P1006 [NOIP2008 提高组] 传纸条

题目

题目链接

题解

四维DP。

我习惯将行数定义为n，列数定义为m。

dp[i][j][p][q]可以理解为A从(1,1)传纸条到(i,j)，B也从(1,1)传纸条到(p,q)，二者不能经过同一个人的最大值。所以dp[n][m][n][m]即为答案。

对于A而言，如果纸条落到了(i,j)手中，那么一定要么是(i-1,j)，要么是(i,j-1)给到(i,j)的，同理，到达(p,q)的纸条也只能来自(p-1,q)或(p,q-1)。转移方程就有了。特判一下如果(i,j)=(p,q)，跳过。

但是如果(i,j)=(p,q)时跳过，那么dp[n][m][n][m]就等于0了，所以我们需要单独处理一下dp[n][m][n][m]。 两张纸条都到达(n,m)无非就两种情形： A的纸条从(n-1,m)传到(n,m)同时B的纸条只能选择从(n,m-1)传到(n,m)； A的纸条从(n,m-1)传到(n,m)同时B的纸条只能选择从(n-1,m)传到(n,m)； 所以只要取二者的max即可。

还有网上很多转移方程都是特判(i,j)=(p,q)，相等则减去一个a[i][j]，感觉没有道理，我这样理解比较有道理。

代码

// 传纸条 https://www.luogu.com.cn/problem/P1006 
#include
using namespace std;
const int N = 55;

int dp[N][N][N][N];
int a[N][N], n, m;

int main()
{
	cin >> n >> m;
	for (int i = 1;i  a[i][j];
			
	for (int i = 1;i