洛谷P1006 [NOIP2008 提高组] 传纸条

题目链接：P1006 [NOIP2008 提高组] 传纸条

题意：网格图， $(1,1)$ 到 $(n,m)$ 找两条不重合的路径，最大价值
注：原题是 $(m,n)$ ，但我不习惯，所以就用 $(n,m)$ 替代（即 $n$ 行 $m$ 列）！

解法一

最烂解法 ，但是能通过此题

设 $dp[i][j][k][l]$ 表示第一条路径到 $(i,j)$ 的位置，第二条路径到 $(k,l)$ 的位置，能获得的最大价值

由于两条路径正着走反着走都一样，所以我们可以看作从 $(1,1)$ 到 $(n,m)$ 的两条不重合的路径

那么显然

$dp[i][j][k][l] = \\ \max\{dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]\}+a[i][j]+a[k][l]$

因为不重复，所以当 $i=k,j=l$ 时要减去 $a[i][j]$

时间复杂度 $O(n^4)$

空间复杂度 $O(n^4)$

伪代码如下（懒的写了…）

for i=1 to n:
	for j=1 to m:
		for k=1 to n:
			for l=1 to m:
dp[i][j][k][l]=max{dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]}+a[i][j]+!((i==k&&j==l))*a[k][l];

答案就是 $dp[n][m][n][m]$

呕～这代码够烂的

解法二

我们观察每个路径，由于它一定是一个斜线方向的（即只能右移下移）

我们知道一个点的纵坐标，那么它的横坐标就是横纵坐标之和减去纵坐标

而两条路径的长度一定是相等的

那么就不用记录点的坐标了

设 $dp[k][i][j]$ 表示横纵坐标和为 $k$ ，第一条路径终点纵坐标为 $i$ ，第二条路径终点纵坐标为 $j$ 时能获得的最大价值

那么显然

$dp[k][i][j]=\\\max\{dp[k-1][i-1][j],dp[k-1][i][j-1],dp[k-1][i][j],dp[k-1][i-1][j-1]\}+a[k-i][i]+a[k-j][j]$

我们发现 $k$ 和 $k-1$ 的答案有关

那么我们可以弄个滚动数组，注意顺序即可通过此题

时间复杂度 $O(n^3)$

空间复杂度 $O(n^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define R register
#define max4(a,b,c,d) max(max((a),(b)),max((c),(d)))
template<typename T>inline void read(R T &k)
{
	R char ch=getchar();R T x=0,f=1;
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	k=x*f;
}
int n,m;
int a[55][55];
int dp[55][55];
signed main()
{
	read(n);read(m);
	for(R int i=1; i<=n; i++)
		for(R int j=1; j<=m; j++)
			read(a[i][j]);
	
	for(R int k=3; k<=m+n-1; k++)
		for(R int i=min(k-2,m-1); i>=1&&k-i<=n; i--) // 注意不要越界了
			for(R int j=min(k-1,m); j>i&&k-j<=n; j--) // 两条路径不重合
				dp[i][j]=max4(dp[i-1][j],dp[i][j-1],dp[i][j],dp[i-1][j-1])+a[k-i][i]+a[k-j][j];
	printf("%lld\n",dp[m-1][m]); // 两条路径不重合	
	return 0;
}