解题思路:
双线程dp,看成两人同时从起点出发。四维数组存储到达该位置时取的数之和。
注意事项:
参考代码:
#include <iostream> #include <algorithm> #include<string.h> using namespace std; int main() { int n,a,b,c; cin>>n; int dp[n+5][n+5][n+5][n+5],f[n+5][n+5]; memset(dp,0,sizeof(dp)); memset(f,0,sizeof(f)); while(cin>>a>>b>>c){ if(a==0&&b==0&&c==0)break; f[a][b]=c; } dp[1][1][1][1]=f[1][1]; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int x=1;x<=n;x++){ for(int y=1;y<=n;y++){ if((i+j)!=(x+y))continue; dp[i][j][x][y]=max(max(dp[i][j-1][x-1][y],dp[i-1][j][x-1][y]),max(dp[i][j-1][x][y-1],dp[i-1][j][x][y-1])); if(i==x&&j==y)dp[i][j][x][y]+=f[i][j]; else dp[i][j][x][y]+=f[i][j]+f[x][y]; } } } } cout<<dp[n][n][n][n]; return 0; }
0.0分
3 人评分
汽水瓶 (C语言代码)浏览:705 |
C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 (C++代码)(手动优化一下计算)浏览:1284 |
回文串 (C语言代码)浏览:2859 |
P1001 (C语言代码)浏览:801 |
简单的a+b (C语言代码)浏览:340 |
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:672 |
蚂蚁感冒 (C语言代码)浏览:1335 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:597 |
矩阵的对角线之和 (C语言代码)浏览:1356 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:775 |