CodeForces 762D Maximum path

http://codeforces.com/problemset/problem/762/D

因为是3*n很巧妙的地方是 往左走两步或更多的走法都可以用往回走以一步

并走完一列来替换 那么走的方法就大大减少 左边一列转移到右边一列 每个

格子的转移方法枚举出来 用动态规划即可解决

最主要的是因为他能够往回走.
但是我们画图可以发现:每次往回走一定不用超过1次.
也就是说，最多只能走成这样

而不会走成这样

因为下图的走法一定可以用上图组合，并且
由于只用3行的特性，每次向回走实际上是取走了所有的数.
所以我们只采用上图方式得出来的答案一定最优

 #include <bits/stdc++.h>

 #define INF 0x7fffffff

 using namespace std;

 typedef long long LL;

 LL grid[][];

 LL tmp[][];

 LL dp[][];

 int main()

 {

     int n;

     scanf("%d", &n);

     for (int i = ; i < ; i++)

     for (int j = ; j < n; j++)

     {

         scanf("%lld", &grid[i][j]);

     }

     dp[][] = grid[][];

     dp[][] = grid[][] + grid[][];

     dp[][] = grid[][] + grid[][] + grid[][];

     tmp[][] = grid[][];

     tmp[][] = grid[][];

     tmp[][] = grid[][];

     for(int j = ;j < n; j++)

     {

         for (int i = ; i < ; i++)

         {

             dp[i][j] = tmp[i][j] = dp[i][j-] + grid[i][j];

         }//这样的转移走法 包括了所有的走法

         dp[][j] = max(dp[][j], tmp[][j] + grid[][j]);

         dp[][j] = max(dp[][j], tmp[][j] + grid[][j] + grid[][j]);

         dp[][j] = max(dp[][j], tmp[][j] + grid[][j]);

         dp[][j] = max(dp[][j], tmp[][j] + grid[][j]);

         dp[][j] = max(dp[][j], tmp[][j] + grid[][j]);

         dp[][j] = max(dp[][j], tmp[][j] + grid[][j] + grid[][j]);

         dp[][j] = max(dp[][j], tmp[][j-] + grid[][j] + grid[][j] + grid[][j-] + grid[][j-] + grid[][j]);

         dp[][j] = max(dp[][j], tmp[][j-] + grid[][j] + grid[][j] + grid[][j-] + grid[][j-] + grid[][j]);

     }

     cout << dp[][n-] << endl;

     return ;

 }

dp[i][j] i 行 j 列可以得到的最大值

tmp[i][j]直接从右边一个走过来的得到的值