思路:双线程 dp
这一题的话,题目其实是可以稍微转化一下的额,一个人走两遍跟两个人同时同速度一人走一格是等价的,
就相当于i+j==i1+j1,这表示一人走一格;
然后就比较简单了。dp[i][j][i1][j1]表示两个人在(i, j)和(i1, j1)所能得到的最大值;
注意事项:
参考代码:
#include<stdio.h> #include<string.h> #define Max(a,b) a>b?a:b int main() { int n,s,x,y,i,j,i1,j1;int a[11][11];int dp[12][12][12][12]; scanf("%d\n",&n); memset(dp,0,sizeof(dp)); while(1) {scanf("%d%d%d",&x,&y,&s); if(x==0&&y==0&&s==0)break;//输入终止 else a[x][y]=s; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(i1=1;i1<=n;i1++) for(j1=1;j1<=n;j1++) { if(i+j!=i1+j1)continue;//不是一人一步 int tem=Max(dp[i-1][j][i1][j1-1],dp[i-1][j][i1-1][j1]); tem=Max(tem,dp[i][j-1][i1][j1-1]); tem=Max(tem,dp[i][j-1][i1-1][j1]); if(i==i1&&j==j1)dp[i][j][i1][j1]=a[i][j]+tem; else dp[i][j][i1][j1]=a[i][j]+a[i1][j1]+tem ; } printf("%d\n",dp[n][n][n][n]); return 0; }
0.0分
4 人评分
字符串输入输出函数 (Java代码)浏览:1437 |
C语言程序设计教程(第三版)课后习题9.1 (Java代码)浏览:471 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:738 |
最长单词 (C语言代码)浏览:1363 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:957 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:676 |
C二级辅导-计负均正 (C语言代码)浏览:480 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:463 |
1052题解(链表操作)浏览:653 |
字符删除 (C语言代码)浏览:715 |