//CodeForces 132C
1 #include"iostream" 2 #include"cstdio" 3 #include"cstring" 4 #include"algorithm" 5 using namespace std; //状态可达dp，其实 bool dp[110][55][220][2]; 就好 6 int dp[110][55][220][2]; //四维状态分别为：当前命令下标，逻辑空间限制（调整命令的次数）转物理空间限制，当前直线位置（设初始位置在 len 处），当前行进方向 7 char cmd[110]; 8 int n; 9 //dp[i][j][l]中存放的是有符号数表示的向量，一开始构造的状态是：当前命令下标，逻辑空间限制（调整命令的次数）转物理空间限制，当前行进方向，这样的话就会不断选取绝对值较大的值作为 dp[i][j][l] 的值，初始化的话肯定是将数组 dp 初始化为绝对值最小的 0 10 //但是对于状态 [i][j][k] ，可能存在关于原点对应的两个位置同时取到最大的绝对值，这时候我们就必须舍去其中一个值，且有可能去掉的值就是最优解的祖先状态，这样就会得到一个错误的结果。11 //于是我们必须加入一维状态用于记录位置向量的方向信息，dp[i][j][k][l],[k] 表示位置向量的方向，0 为正向，1 为 反向12 //当dp[i][j][k][l] == 0 时,dp[i][j][0][l] 和 dp[i][j][1][l] 分别为正负半轴上的两个 0 点，互不影响，且在两个 0 点处dp值又相等（均为0），恰好又满足了相互统一的性质，所以我们在做状态转移的时候不用担心作为前驱状态的 0 点是另一半轴的点从而发生 k 值变化的麻烦情况，因为我们在需要选取 0 点时，只选取处于同侧的 0 点即可13 //而且在状态转移过程中，dp[i][j][k][l]，不可能会取到负值，但是在 test 16 上 wa 了...于是最后就改成了最初提到的这种写法14 15 int main()16 {17 int i,j,k,l,len,pre_pos,res = 0;18 scanf("%s%d",cmd+1,&n);19 len = strlen(cmd+1);20 dp[0][0][len][0] = 1; //状态起点，因为在直线上行进存在两个方向，具有对称性，所以我们只选取一个方向为初始状态即可， 0 表示正向， 1 表示反向21 for(i = 1; i<=len; ++i) {22 for(j = 0; j<=n; ++j) {23 for(k = 0; k<=(len<<1); ++k) {24 for(l = 0; l<2; ++l) {25 if(cmd[i]=='T') {26 pre_pos = k+(l==0?-1:1);27 if(dp[i-1][j][k][l^1]) //（前一状态接受 ‘T’）28 dp[i][j][k][l] = 1;29 else if(j>=1&&pre_pos>=0&&pre_pos<=(len<<1)&&dp[i-1][j-1][pre_pos][l]) //（前一状态拒绝 ‘T’）30 dp[i][j][k][l] = 1;31 }32 else {33 pre_pos = k+(l==0?-1:1);34 if(pre_pos>=0&&pre_pos<=(len<<1)&&dp[i-1][j][pre_pos][l]) //（前一状态接受 ‘F’）35 dp[i][j][k][l] = 1;36 else if(j>=1&&dp[i-1][j-1][k][l^1]) //（前一状态拒绝 ‘F’）37 dp[i][j][k][l] = 1;38 }39 }40 }41 }42 }43 for(j = n; j>=0; j -= 2) { //对同一 cmd[i] 可以多次更改，且 cmd[i]只有两种状态，意味着可以留下偶数次调整命令的机会不使用44 for(k = 0; k<=(len<<1); ++k) {45 for(l = 0; l<2; ++l) {46 if(dp[len][j][k][l]) {47 res = max(res,abs(k-len));48 }49 }50 }51 }52 printf("%d\n",res);53 return 0;54 }
wa 在 test 16 上的写法
1 #include"iostream" 2 #include"cstdio" 3 #include"cstring" 4 #include"algorithm" 5 using namespace std; 6 int dp[110][55][2][2]; 7 char cmd[110]; 8 int n,len; 9 int main()10 {11 int i,j,k,l,res = 0;12 scanf("%s%d",cmd+1,&n);13 len = strlen(cmd+1);14 memset(dp,-1,sizeof(dp));15 dp[0][0][0][0] = 0;16 for(i = 1; i<=len; ++i) {17 for(j = 0; j<=n; ++j) {18 for(k = 0; k<2; ++k) {19 for(l = 0; l<2; ++l) {20 if(cmd[i]=='T') {21 dp[i][j][k][l] = max(dp[i][j][k][l],dp[i-1][j][k][l^1]);22 if(j>=1&&dp[i][j][k][l] =1&&dp[i][j][k][l] =0; j -= 2) {42 for(k = 0; k<2; ++k) {43 for(l = 0; l<2; ++l) {44 res = max(res,dp[len][j][k][l]);45 }46 }47 }48 printf("%d\n",res);49 return 0;50 } 
测试数据：http://codeforces.com/contest/132/submission/2521716
反思：选取位置坐标作为状态的 dp 所写的程序不仅有较好的可读性和较低的实现难度，最关键的是需要特殊考虑的情况比只选取正负半轴标记作为状态的 dp 要少很多，充分体现了位置坐标状态的优越性。
扩展：这题网上有人用记忆化搜索过的，先挖个坑，随后补上