坐标类DP

例题引入

例1

这里k和L的取值很重要，其实也就是判断从这个方向来的是不是最佳路径。

注意：判断参数时两个if互不干扰。

例2

题目见P1006

题目节选：

小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。

一来一回的要求说明贪心思想不可行：

那么既然~~光路可逆~~路线可逆，那么就视为两张一起传。
其实说得直接一点，题目所求就是两条加在一起最大而无重叠的路线。

所以审清题后，我们推出这个图应该长这样：

用dp实现就是计算目前的最大值。于是要表示两张纸条的坐标，可以定义f(i1,j1,i2,j2)为当前最大值。所以推状态转移方程：

f(i1,j1,i2,j2)=max \begin{cases} f(i1-1,j1,i2-1,j2) \\ f(i1-1,j1-1,i2-1,j2) \\ f(i1-1,j1,i2-1,j2-1) \\ f(i1-1,j1-1,i2-1,j2-1) \end{cases}

不过四维多少大了点，试试降维。用f(k,i,j)表示当前最大值。k=step,i=x1,j=x2。所以y1=k-i,y2=k-j。状态转移方程略（类比降维前，很好理解）。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;

int m,n;
int c[107][107];
long long f[107][107][107];

int main()
{
	cin>>m>>n;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>c[i][j];
		}
	}
	f[1][2][1]=f[1][1][2]=c[2][1]+c[1][2];
	for(int k=2;k<m+n-1;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(i!=j||k==m+n-2)
				{
					if(k-i+2<=m&&k-j+2<=m&&i<=k+1&&j<=k+1)
					{
						f[k][i][j]=max(f[k-1][i][j],max(f[k-1][i-1][j],max(f[k-1][i][j-1],f[k-1][i-1][j-1])))+c[k-i+2][i]+c[k-j+2][j];
						//cout<<"k="<<k<<" i="<<i<<" j="<<j<<" f="<<f[k][i][j]<<endl;	
					}	
				}
			}
		}
	}
	f[m+n-1][n][n]=max(f[m+n-2][n][n],max(f[m+n-2][n-1][n],max(f[m+n-2][n][n-1],f[m+n-2][n-1][n-1])));
	cout<<f[m+n-1][n][n]<<endl;
	return 0;
}

注意：

本代码步数设置为n+m-2，及移动次数，算纵坐标是要加2的。
坐标不能重叠或超出范围。
到达终点时，坐标可能发生重叠。
第一部只能向（1，2）和（2，1）走，不能是其他坐标，所以循环从k=2开始。

坐标类DP

文章操作

坐标类DP

例题引入

例1

例2

相关推荐

评论

坐标类DP