驾校报名网站怎么做/我想学做互联网怎么入手
1875: 蛤玮的财宝
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 470 Solved: 98
SubmitStatusWeb Board
Description
蛤玮和他的妹子出海游玩,不小心遭遇了海难,他们醒来之后发现自己到了一座金银岛.岛主非常好心的告诉他们在岛的另一边有船可以送他们回家.
这座岛可以看成n*m的矩阵,蛤玮他们在位置(1,1),而船在位置(n,m).蛤玮发现金银岛遍地都是金子,每个格子里有价值a[i,j]的金子,他和妹子打算在回去的路上带一些走.如果他们路过了位置(i,j),就可以假装系鞋带捡走地上的金子.为了不引起怀疑,他们在走的时候只能往接近码头的方向走,即如果蛤玮现在在(i,j),他只能移动到(i+1,j)或者(i,j+1).为了能拿走更多的金子,蛤玮和妹子决定装作互相不认识,这样他们就可以分开走,从而拿到更多的金子.
蛤玮和他妹子想知道他们最多能拿走多少金子.
注意如果蛤玮和他妹子经过了相同的地方,只能得到一次金子,因为地上的捡完就没有了.
Input
T(1<=T<=10),表示数据组数.
每组数据第一行n,m(1<=n,m<=100),接下来n行,每行m个数,第i行第j列的值a[i,j](1<=a[i,j]<=1000)表示位置(i,j)的金子的价值.
Output
每组数据输出一行,蛤玮和他妹子能拿到的金子总价的最大值.
Sample Input
12 22 11 2
Sample Output
6
HINT
Source
题解：
dp[k][i][j]:当前在两个人都走了k步的前提下，两个人的x坐标
你要知道，下次要两人x坐标到达i，j时，有四种情况：
1.第一个人往右，第二个人向下
2.第一个人向右，第二个人向右
3.第一个人向下，第二个人向下
4.第一个人向下，第二个人向右
由此便可轻易列出递推公式了（详见代码）
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#include<algorithm>
using namespace std;
#define maxn 105
int dp[maxn*2][maxn][maxn],a[maxn][maxn];
int main()
{int T,n,m,i,j,k,step,ans;scanf("%d",&T);while(T--){ans=0;memset(a,0,sizeof(a));memset(dp,0,sizeof(dp));scanf("%d%d",&n,&m);for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&a[i][j]);step=n+m-2;for(i=1;i<=n;i++)//枚举男的x坐标for(j=1;j<=n;j++)//枚举女的x坐标for(k=1;k<step;k++)//当前走了多少步{if(i==j)//两条路线不能有交点break;if(k+2>=i && k+2>=j)dp[k][i][j]=max(max(dp[k-1][i][j],dp[k-1][i-1][j-1]),max(dp[k-1][i][j-1],dp[k-1][i-1][j]))+a[i][k+2-i]+a[j][k+2-j];}ans=max(dp[step-1][n-1][n],dp[step-1][n][n-1])+a[n][m]+a[1][1];printf("%d\n",ans);}
}