【题解】洛谷P1006传纸条

链接

https://www.luogu.org/problemnew/show/P1006

日常牢骚

过年前最后一节课上完了坐标DP 也接触了一点区间DP（noi1995石子合并）下次做做看看吧

老师布置了好多道DP这让我这个刚刚学的蒟蒻可咋办呀

想die的心

正题

不扯淡了赶紧扯回来

首先看到这题我想到了另外一题很相似的叫啥我忘了......

反正也是双向DP（姑且这么叫吧）

看到题解里有dalao们弄成三维的二维的甚至是一维的

我只想说

对大佬%%%%%%%%

本蒟蒻的做法十分质朴淡雅清新脱俗

因为题目的数据挺小只有50

所以自然而然用到了四维......

思路

既然是从头尾各走一遍且不重复那么我们可以看成从头走两遍不重复的求最大的好感度
于是我们设(x1,y1）为第一次的坐标（x2，y2)为第二次的坐标得出f[x1][y1][x2][y2]为好感度总和
那么只有四种方法可以到每一个格子（一上，二上）（一上，二左）（一左，二上）（一左，二左）
最后从后面遍历到头就出答案 答案在f[2][1][1][2]中（因为不重复所以只可能一个在下面一个在左边）

代码

#include<iostream>

using namespace std;

int f[51][51][51][51],a[51][51];

int n,m;

int main()

{

	cin>>m>>n;

	for(int i=1;i<=m;i++)

	for(int j=1;j<=n;j++)

	cin>>a[i][j];

	for(int x1=m;x1>=1;x1--)//从后面开始遍历回去

	for(int y1=n;y1>=1;y1--)

	for(int x2=m;x2>=1;x2--)

	for(int y2=n;y2>=1;y2--)

	{

		if((x1>1&&x2>1)&&((x1-1!=x2-1)||(y1!=y2)))

		f[x1-1][y1][x2-1][y2]=max(f[x1][y1][x2][y2]+a[x1-1][y1]+a[x2-1][y2],f[x1-1][y1][x2-1][y2]);

		if((x1>1&&y2>1)&&((x1-1!=x2)||(y1!=y2-1)))

		f[x1-1][y1][x2][y2-1]=max(f[x1][y1][x2][y2]+a[x1-1][y1]+a[x2][y2-1],f[x1-1][y1][x2][y2-1]);

		if((y1>1&&x2>1)&&((x1!=x2-1)||(y1-1!=y2)))

		f[x1][y1-1][x2-1][y2]=max(f[x1][y1][x2][y2]+a[x1][y1-1]+a[x2-1][y2],f[x1][y1-1][x2-1][y2]);

		if((y1>1&&y2>1)&&((x1!=x2)||(y1-1!=y2-1)))

		f[x1][y1-1][x2][y2-1]=max(f[x1][y1][x2][y2]+a[x1][y1-1]+a[x2][y2-1],f[x1][y1-1][x2][y2-1]);

	}

	cout<<f[2][1][1][2];//答案

}

巴特西

【题解】洛谷P1006传纸条

链接

日常牢骚

正题

思路

代码

最新文章

热门文章