多维dp

佚名 7年前 (2019-04-16) 随笔 1502人围观抢沙发百度已收录

P1006 传纸条我的第一道多维dp

我第一眼看到这道题就知道不会因为从来没见过

后来看了神仙的题解恍然大悟然而自己写的时候还是有bug（逃

这里给出一个三维数组的解法（oi爷太强了

首先，要找来回两条路径，这样考虑太麻烦，把它转化为两个人从1,1这点一起走，一直走到n,m这点所经过的路径。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

定义dp[p][i][j]表示当前走了p步，第一个人走到第i行，第二个人走到第j行的最大价值。

显然两个人的坐标都可以计算出来，第一个人是(i,p-i+1)，第二个人是(j,p-j+1).

那么状态转移方程呼之欲出就是

dp[p][i][j]=max(dp[p-1][i][j],dp[p-1][i-1][j],dp[p-1][i-1][j-1],dp[p-1][i][j-1])+num[i][p-i+1]+num[j][p-j+1];

不要以为到这就结束了！

在循环时我们一定要判断！！

判断什么呢当i=j时代表他们坐标重复了（想想为什么所以这时候价值只能算i j其中一个的

还有一点！循环时双层循环全部要到m 而不是一个n一个m 因为这里的 i j 全部代表层数

还有一点（我wa掉的一点就是双层for不仅要判断层数小于m 而且要判断当前步数小于总步数

要不然会wa掉第二个点（逃

接下来放代码

#define rep(i,a,b) for(int i=a;i<=b;i++)
#include <stdio.h>
#include <iostream>
using namespace std;
const int e=55;
int dp[2*e][e][e],num[e][e];
int n,m;
int maxx(int a,int b,int c,int d)
{
	if(a<b)
		a=b;
	if(c>a)
		a=c;
	if(d>a)
		a=d;
	return a;
}
int main(int argc, char const *argv[])
{
	cin >> m >> n;
	rep(i,1,m){
		rep(j,1,n){
			cin >> num[i][j];
		}
	}
	dp[1][1][1]=num[1][1];
	rep(p,2,n+m-1){
		for(int i=1;i<=m&&i<=p;i++){
			for(int j=1;j<=m&&j<=p;j++){
				dp[p][i][j]=maxx(dp[p-1][i][j],dp[p-1][i-1][j-1],dp[p-1][i][j-1],dp[p-1][i-1][j]);
				int sum;
				if(i==j)
					sum=num[j][p-j+1];
				else
					sum=num[i][p-i+1]+num[j][p-j+1];
				dp[p][i][j]+=sum;
			}
		}
	}
	printf("%d\n", dp[n+m-1][m][m]);
	return 0;
}