Educational Codeforces Round 17 D dp

题目链接：http://codeforces.com/contest/762/problem/D

题意：n*3的方格，从左上走到右下，一个格子不能走两遍，每个格子有个权值，最后将路径所有权值加起来问最大是多少？

思路：瞎dp分类讨论一下，竖着三个三个去刷dp的表，直接分类讨论可能由哪些转移过来就好。

备注：假期摸鱼。。

代码：

#include<bits/stdc++.h>
#define bug(x) cout<<"bug "<<x<<endl;
using namespace std;
#define ll long long
const int maxn=1e6+10;
const ll inf=1e18+10;
int n;
ll dp[maxn][3];
ll arr[maxn][3];


int main(){
    cin>>n;
    memset(arr,0,sizeof(arr));
    for(int i=0;i<3;i++){
        for(int j=1;j<=n;j++){
            cin>>arr[j][i];
            dp[j][i]=-inf;
        }
    }
    dp[1][0]=arr[1][0];
    dp[1][1]=dp[1][0]+arr[1][1];
    dp[1][2]=dp[1][1]+arr[1][2];
    for(int i=2;i<=n;i++){
        dp[i][0]=max(dp[i][0],dp[i-1][0]);
        dp[i][0]=max(dp[i][0],dp[i-1][1]+arr[i][1]);
        dp[i][0]=max(dp[i][0],dp[i-1][2]+arr[i][1]+arr[i][2]);
        dp[i][0]=max(dp[i][0],dp[i-2][2]+arr[i-1][0]+arr[i-1][1]+arr[i-1][2]+arr[i][1]+arr[i][2]);
        dp[i][0]+=arr[i][0];

        dp[i][1]=max(dp[i][1],dp[i-1][1]);
        dp[i][1]=max(dp[i][1],dp[i-1][0]+arr[i][0]);
        dp[i][1]=max(dp[i][1],dp[i-1][2]+arr[i][2]);
        dp[i][1]+=arr[i][1];

        dp[i][2]=max(dp[i][2],dp[i-1][2]);
        dp[i][2]=max(dp[i][2],dp[i-1][1]+arr[i][1]);
        dp[i][2]=max(dp[i][2],dp[i-1][0]+arr[i][1]+arr[i][0]);
        dp[i][2]=max(dp[i][2],dp[i-2][0]+arr[i-1][0]+arr[i-1][1]+arr[i-1][2]+arr[i][1]+arr[i][0]);
        dp[i][2]+=arr[i][2];
    }
    cout<<dp[n][2]<<endl;
    return 0;
}