Codeforces GYM 101147H. Commandos
传送门：http://codeforces.com/gym/101147/problem/H
题目翻译
一个( \left ( 10 \times 10 \times 10 \right ) )的正方体，每个格子有数字。一开始在( \left ( 10,1,1 \right ) )，每次只能从( \left ( f,x,y \right ) )，去往( \left ( f-1,x,y \right ) )、( \left ( f,x+1,y \right ) )、( \left ( f,x,y+1 \right ) )。问最多能获得的数字和。
题解
直接按顺序递推DP即可
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
//while(true) RP++; #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; const int Maxn=10+5; int hostage[Maxn][Maxn][Maxn]; int dp[Maxn][Maxn][Maxn]; int n; inline void solve(int T){ memset(dp,0,sizeof(dp)); memset(hostage,0,sizeof(hostage)); scanf("%d",&n); for (int i=1;i<=n;i++){ int f,x,y,h; scanf("%d%d%d%d",&f,&x,&y,&h); hostage[f][x][y]=h; } int Ans=0; for (int f=10;f>=1;f--){ for (int x=1;x<=10;x++){ for (int y=1;y<=10;y++){ dp[f][x][y]+=hostage[f][x][y]; Ans=max(Ans,dp[f][x][y]); if (f>1) dp[f-1][x][y]=max(dp[f][x][y],dp[f-1][x][y]); if (x<10) dp[f][x+1][y]=max(dp[f][x][y],dp[f][x+1][y]); if (y<10) dp[f][x][y+1]=max(dp[f][x][y],dp[f][x][y+1]); } } } printf("%d\n",Ans); } int main(){ freopen("commandos.in","r",stdin); int T=0; while(scanf("%d",&T)!=EOF) for (int i=1;i<=T;i++) solve(i); return 0; } |
原文链接：Codeforces GYM 101147H. Commandos
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!