洛谷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;
}