//CodeForces 132C
之前 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,0xf3,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]<dp[i-1][j-1][k][l]+(k^l?-1:1)) { 23 dp[i][j][k][l] = dp[i-1][j-1][k][l]+(k^l?-1:1); 24 } 25 } 26 else { 27 if(dp[i][j][k][l]<dp[i-1][j][k][l]+(k^l?-1:1)) { 28 dp[i][j][k][l] = dp[i-1][j][k][l]+(k^l?-1:1); 29 } 30 if(j>=1&&dp[i][j][k][l]<dp[i-1][j-1][k][l^1]) { 31 dp[i][j][k][l] = dp[i-1][j-1][k][l^1]; 32 } 33 } 34 if(dp[i][j][k][l]==0) { 35 dp[i][j][k^1][l] = max(0,dp[i][j][k^1][l]); 36 } 37 } 38 } 39 } 40 } 41 for(j = n; j>=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 ",res); 49 return 0; 50 }
//换一种清爽的写法
1 #include "iostream" 2 #include "cstdio" 3 #include "cstring" 4 #include "algorithm" 5 using namespace std; 6 int dp[110][55][2][2]; 7 int n ,m; 8 char cmd[110]; 9 10 int main() 11 { 12 scanf("%s%d", cmd + 1, &m); 13 int i, j, k, t; 14 n = strlen(cmd + 1); 15 memset(dp, 0xf3, sizeof(dp)); 16 dp[0][0][0][0] = 0; 17 for(i = 1; i <= n; ++i) { 18 for(j = 0; j<=m; ++j) { 19 for(k = 0; k<=1; ++k) { 20 if(cmd[i]=='F') { 21 if(j >= 1) { 22 dp[i][j][k][0] = max(dp[i - 1][j][k][0] + ((k==0)?1:-1), dp[i - 1][j - 1][k][1]); 23 dp[i][j][k][1] = max(dp[i - 1][j][k][1] + ((k==1)?1:-1), dp[i - 1][j - 1][k][0]); 24 } 25 else { 26 dp[i][j][k][0] = dp[i - 1][j][k][0] + ((k==0)?1:-1); 27 dp[i][j][k][1] = dp[i - 1][j][k][1] + ((k==1)?1:-1); 28 } 29 } 30 else { 31 if(j >= 1) { 32 dp[i][j][k][0] = max(dp[i - 1][j - 1][k][0] + ((k==0)?1:-1), dp[i - 1][j][k][1]); 33 dp[i][j][k][1] = max(dp[i - 1][j - 1][k][1] + ((k==1)?1:-1), dp[i - 1][j][k][0]); 34 } 35 else { 36 dp[i][j][k][0] = dp[i - 1][j][k][1]; 37 dp[i][j][k][1] = dp[i - 1][j][k][0]; 38 } 39 } 40 if(dp[i][j][k][0]==0) 41 dp[i][j][k^1][0] = max(dp[i][j][k^1][0], 0); 42 if(dp[i][j][k][1]==0) 43 dp[i][j][k^1][1] = max(dp[i][j][k^1][1], 0); 44 } 45 } 46 } 47 int res = 0; 48 for(j = m; j>=0; j -= 2) 49 for(k = 0; k<=1; ++k) 50 for(t = 0; t<=1; ++t) 51 res = max(res, dp[n][j][k][t]); 52 printf("%d ", res); 53 }
//然后我脑子一抽，想通过把原点设在理论活动范围最左端的方法把 第三维状态 去掉，但是写出了 距离出发点相同距离 异侧的两个点的情况合并成一种情况 的错误 dp......
至于为什么不能讲异侧的两个点合并起来，我在之前的某一篇随笔中应该有过说明，这里就不提了
//而且初始化也有问题，如果把 dp[0] 中的所有元素全部初始化成 100，那么就相当于加入了很多错误的起始状态；全部初始化成 0 那么相当于这些点一开始就在最左端，还是不对；所以应该将除 dp[0][0][0] 以外的整个 dp 数组全部初始化为合法取值范围以外的值，如 -1 ，每次在做状态转移之前都要对状态前驱做一次合法性检查
//错误 dp 也贴出来吧......
1 #include "iostream" 2 #include "cstdio" 3 #include "cstring" 4 #include "algorithm" 5 using namespace std; 6 int dp[110][55][2]; 7 int n, m; 8 char cmd[110]; 9 10 int main() 11 { 12 int i, j, k, tmp_1, tmp_2; 13 scanf("%s%d",cmd + 1, &m); 14 n = strlen(cmd+1); 15 16 for(j = 0; j<=m; ++j) 17 for(k = 0; k<2; ++k) 18 dp[0][j][k] = 100; 19 20 for(i = 1; i<=n; ++i) { 21 for(j = 0; j<=m; ++j) { 22 for(k = 0; k<2; ++k) { 23 dp[i][j][k] = tmp_1 = tmp_2 = 100; 24 if(cmd[i]=='F') { 25 tmp_1 = dp[i-1][j][k] + (k==0?1:-1); 26 if(j>=1) 27 tmp_2 = dp[i-1][j-1][k^1]; 28 } 29 else { 30 tmp_1 = dp[i-1][j][k^1]; 31 if(j>=1) 32 tmp_2 = dp[i-1][j-1][k] + (k==0?1:-1); 33 } 34 if(abs(tmp_1 - 100)>abs(tmp_2 - 100)) 35 dp[i][j][k] = tmp_1; 36 else 37 dp[i][j][k] = tmp_2; 38 } 39 } 40 } 41 42 int res = 0; 43 for(j = m; j>=0; j -= 2) 44 for(k = 0; k<2; ++k) 45 res = max(res, abs(dp[n][j][k] - 100)); 46 printf("%d ",res); 47 }