CodeForces 429 B Working out（递推dp）

时间：2023-03-09 00:20:29
CodeForces 429 B Working out（递推dp）

　　题目连接：B. Working out

　　我想了很久都没有想到怎么递推，看了题解后试着自己写，结果第二组数据就 wa 了，后来才知道自己没有判选择的两条路径是否只是一个交点。

　　大概思路是：先预处理出每个格子到四个角落格子的路径最大数值，然后枚举两个人相遇的交点格子，枚举 A、B 的进来和出去方式（记两个线路为  1 和 2，考虑一个公共点，1 为左进右出，2 为下进上出；1 上进下出，2 为左进右出），然后求最大值即可。

　　注意边界情况。

　　原题解链接：http://blog.****.net/cc_again/article/details/25691925， http://blog.****.net/qq574857122/article/details/25625151

　　我的代码：（全用宏定义了 -_-|| ）

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 #define  sd(x)  scanf("%d",&(x))

 #define  sd2(x,y)  scanf("%d %d",&(x),&(y))

 typedef long long LL;

 LL dp[][][], a[][];

 #define  For(i,s,t)   for(int i = s; i <= t; ++i)

 #define  desFor(i,t,s)   for(int i = t; i >= s; --i)

 int main() {

     int n,m;

     while(~sd2(n,m)) {

         For(k,,)  For(i,,n+)

             dp[k][i][m + ] = ;

         For(k,,)  For(j,,m+)

             dp[k][n + ][j] = ;

         For(i,,n)  For(j,,m)

             sd(a[i][j]);

         // 递推预处理出所有交点到 4 个角的最大值

         For(i,,n)  For(j,,m)

             dp[][i][j] = max(dp[][i-][j], dp[][i][j-]) + a[i][j];

         For(i,,n)  desFor(j,m,)

             dp[][i][j] = max(dp[][i-][j], dp[][i][j+]) + a[i][j];

         desFor(i,n,)  For(j,,m)

             dp[][i][j] = max(dp[][i+][j], dp[][i][j-]) + a[i][j];

         desFor(i,n,)  desFor(j,m,)

             dp[][i][j] = max(dp[][i+][j], dp[][i][j+]) + a[i][j];

         LL ans = ;

         // 枚举所有交点

         For(i,,n-)  For(j,,m-) {

             // 第一种路径选择： A 从上往下穿过交点 dp[i][j]，B 从左向右穿过 dp[i][j]

             LL first = dp[][i-][j] + dp[][i+][j] + dp[][i][j+] + dp[][i][j-];

             ans = max(ans, first);

             // 第二种路径选择： A 从左向右穿过交点 dp[i][j]，B 从上往下穿过 dp[i][j]

             LL second = dp[][i][j-] + dp[][i][j+] + dp[][i-][j] + dp[][i+][j];

             ans = max(ans, second);

         }

         printf("%I64d\n",ans);

     }

     return ;

 }

相关文章