当前位置：首页 > news >正文

CodeForces 132C 一道简单 dp

news 来源：原创 2024/5/3 21:33:36

//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]<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]) {
35 //                        printf("%d %d %d %d == %d\n",i,j,k,l,dp[i][j][k][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\n",res);
49     return 0;
50 }