专栏文章

题解：P1006 [NOIP 2008 提高组] 传纸条

TTomwsc
P1006题解参与者 7已保存评论 9

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
9 条
当前快照
1 份
快照标识符
@miqbipzk
此快照首次捕获于
2025/12/04 02:06
3 个月前
此快照最后确认于
2025/12/04 02:06
3 个月前
查看原文

P1006 [NOIP 2008 提高组] 传纸条 题解

Myblog
本人习惯先 nn 后 mm，所以下面的 nn 和 mm 均与题目相反。

题意

找出两条从 (1,1)(1,1) 到 (n,m)(n,m) 的路径，使这两条路径之和最大。

思路

考虑 dp。
设 dpi,j,p,qdp_{i,j,p,q} 表示第一条路径走到 (i,j)(i,j)，第二条路径走到 (p,q)(p,q) 的最大值。
接下来我们推方程：
不难发现 (i,j)(i,j) 可以从 (i−1,j)(i-1,j) 和 (i,j−1)(i,j-1) 转移而来，而 (p,q)(p,q) 可以从 (p−1,q)(p-1,q) 和 (p,q−1)(p,q-1) 转移而来。同时，因为是两条路径同时计算，所以转移时还要加上 ai,ja_{i,j} 和 ap,qa_{p,q}。
于是得到转移方程：
dpi,j,p,q=max⁡(dpi−1,j,p−1,q,dpi−1,j,p,q−1,dpi,j−1,p−1,q,dpi,j−1,p,q−1)+ai,j+ap,qdp_{i,j,p,q}=\max(dp_{i-1,j,p-1,q},dp_{i-1,j,p,q-1},dp_{i,j-1,p-1,q},dp_{i,j-1,p,q-1})+a_{i,j}+a_{p,q}
注意到为了使这两条路径不相交，我们还需要改变一下枚举方式。可以让第一条路径只在矩阵的上半部分转移，而剩下的部分便让第二条路径进行转移。于是得到 ii，jj，pp，qq 这 44 个变量的枚举方式：
ii，jj 不变，pp 从 i+1i+1 开始枚举，qq 一直枚举到 j−1j-1。（还是比较容易理解的）
最后，因为这样子 dp 不会相交，所以两条路径不会到达 (n,m)(n,m)。但因为 an,m=0a_{n,m}=0，所以最后答案也就可以转化为：dpn−1,m,n,m−1dp_{n-1,m,n,m-1}。

代码

CPP
#include<bits/stdc++.h>
#define int long long
#define inf 1ll << 62
using namespace std;
const int MAXN = 55;
int n , m;
int a[MAXN][MAXN];
int dp[MAXN][MAXN][MAXN][MAXN];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(register int i = 1;i <= n;i ++)
		for(register int j = 1;j <= m;j ++)
			cin >> a[i][j];
	for(register int i = 1;i <= n;i ++)
		for(register int j = 1;j <= m;j ++)
			for(register int p = i + 1;p <= n;p ++)
				for(register int q = 1;q < j;q ++)
					dp[i][j][p][q] = max(dp[i - 1][j][p - 1][q] , max(dp[i - 1][j][p][q - 1] , max(dp[i][j - 1][p - 1][q] , dp[i][j - 1][p][q - 1]))) + a[i][j] + a[p][q];
	cout << dp[n - 1][m][n][m - 1] << '\n';
	return 0;
}

评论

共 9 条评论，欢迎与作者交流。

正在加载评论...