[Educational Codeforces Round 17 D (762D)] Maximum path

题意

给定一个 3⋅n 的数字矩阵，要求从 (1,1) 走到 (3,n) 使得路径上数字和最大，每个位置只能走一次。

题解

找规律，一条路径不会往回翻多于一格。因为如果多于一格，所有的路径情况都能由不多于一格的路径方案代替。

>>v v>v <<v ==> v^v v>> >^>

那么每一列有5种状态

status 0 1 2 3 4 0 > > -> 1 > < < 2 > -> >

如果某一列状态为0,1或2，代表从这一列有着一些路径从第0,1或2行接出。 如果某一列状态为3，代表着出现一次回翻且回翻是从这一列的第0行进入，下一列的第2行接出，走遍这两列的每个数字。 状态为4的类似状态3。 然后 O(n) dp

代码

/// by ztx /// blog.csdn.net/hzoi_ztx #define Rep(i,l,r) for(i=(l);i<=(r);i++) #define rep(i,l,r) for(i=(l);i< (r);i++) #define Rev(i,r,l) for(i=(r);i>=(l);i--) #define rev(i,r,l) for(i=(r);i> (l);i--) #define Each(i,v) for(i=v.begin();i!=v.end();i++) #define r(x) read(x) typedef long long ll ; typedef double lf ; int CH , NEG ; template <typename TP>inline void read(TP& ret) { ret = NEG = 0 ; while (CH=getchar() , CH<'!') ; if (CH == '-') NEG = true , CH = getchar() ; while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ; if (NEG) ret = -ret ; } #define maxn 100010LL #define infi 1000000000000000LL ll a[3][maxn]; ll f[5][maxn]; inline void MA(ll&x,const ll&y) { if (x < y) x = y; } /* status 0 1 2 3 4 0 > > -> 1 > < < 2 > -> > */ int main() { int n, i, j; ll now; r(n); Rep (i,1,n) r(a[0][i]); Rep (i,1,n) r(a[1][i]); Rep (i,1,n) r(a[2][i]); rep (i,0,5) Rep (j,0,n) f[i][j] = -infi; f[0][0] = 0; Rep (i,1,n) { MA(f[0][i],f[0][i-1]+a[0][i]); MA(f[1][i],f[1][i-1]+a[1][i]); MA(f[2][i],f[2][i-1]+a[2][i]); now = a[0][i]+a[1][i]; MA(f[0][i],f[1][i-1]+now); MA(f[1][i],f[0][i-1]+now); now += a[2][i]; MA(f[0][i],f[2][i-1]+now); MA(f[2][i],f[0][i-1]+now); MA(f[0][i],f[4][i-1]+now); MA(f[2][i],f[3][i-1]+now); MA(f[3][i],f[0][i-1]+now); MA(f[4][i],f[2][i-1]+now); now = a[1][i]+a[2][i]; MA(f[1][i],f[2][i-1]+now); MA(f[2][i],f[1][i-1]+now); } printf("%I64d\n", f[2][n]); END: getchar(), getchar(); return 0; }