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

2019-11-14 10:16:48

字體：大中小

來源：轉載

供稿：網友

題意

給定一個3?n $3/cdot n$ 的數字矩陣，要求從(1,1) $(1,1)$ 走到(3,n) $(3,n)$ 使得路徑上數字和最大，每個位置只能走一次。

題解

找規律，一條路徑不會往回翻多于一格。因為如果多于一格，所有的路徑情況都能由不多于一格的路徑方案代替。

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

那么每一列有5種狀態

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

如果某一列狀態為0,1或2，代表從這一列有著一些路徑從第0,1或2行接出。如果某一列狀態為3，代表著出現一次回翻且回翻是從這一列的第0行進入，下一列的第2行接出，走遍這兩列的每個數字。狀態為4的類似狀態3。然后O(n) $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 1000000000000000LLll 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 40 > > ->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); }