[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); } PRintf("%I64d/n", f[2][n]); END: getchar(), getchar(); return 0;}

上一篇：编译openjdk 时 ALT_BOOTDIR设置

下一篇：1068. Find More Coins (30)

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注