当前位置：首页 > news >正文

信息学奥赛一本通 1853：【08NOIP提高组】传纸条 | 洛谷 P1006 [NOIP 2008 提高组] 传纸条

news 来源：原创 2025/7/2 2:03:24

【题目链接】

ybt 1853：【08NOIP提高组】传纸条
洛谷 P1006 [NOIP 2008 提高组] 传纸条

【题目考点】

1. 动态规划：坐标型动态规划

【解题思路】

抽象问题，存在m乘n的网格，每个格子中有一个数值，即同学愿意帮忙的好心程度。问(1,1)走到(m,n)是第一条路径，从(m,n)到(1,1)是第二条路径，两条路径不相交（即不存在格子同时属于两条路径）。
对于每个可能的从(m,n)到(1,1)的路径，都存在一个从(1,1)到(m,n)的与该路径经过相同格子的路径与其对应。
因此可以认为求的第二条路径也是从(1,1)走到(m,n)的路径。

1. 状态定义

阶段：第一趟走到的位置(i,j)与第二趟走到的位置(k,l)
决策：下一步如何走
策略：第一趟从(1,1)走到(i,j)，第二趟从(1,1)走到(k,l)的路径。
策略集合：第一趟从(1,1)走到(i,j)，第二趟从(1,1)走到(k,l)的所有路径方案。
条件：取到的数字加和最大
统计量：数字加和
状态定义： $dp_{i,j,k,l}$ :第一趟从(1,1)走到(i,j)，第二趟从(1,1)走到(k,l)取到的数字加和最大的路径方案的数字加和。

2. 状态转移方程

记： $a_{i,j}$ 为(i,j)位置的数字。

策略集合：从(1,1)走到(i,j)，再从(1,1)走到(k,l)的路径方案
分割策略集合：根据最后一步如何走到(i,j)，以及如何走到(k,l)分割策略集合

由于每次只能向右或下走，那么第一趟走到(i,j)前，只可能在(i,j)上面一格(i-1,j)或左侧一格(i,j-1)。同理，第二趟走到(k,l)前，只可能在(k-1,l)或(k,l-1)。
因此，第一趟到达(i,j)前的位置与第二趟到达(k,l)前的位置就有4种组合:

(i-1,j)与(k-1,l)
(i,j-1)与(k-1,l)
(i-1,j)与(k,l-1)
(i,j-1)与(k,l-1)

先求出第一趟到达(i,j)前的位置与第二趟到达(k,l)前的位置的路线上的数字加和。
如果(i,j)与(k,l)不是同一位置，路径上数值加和就加上 $a_{i,j}$ 与 $a_{k,l}$ 。
如果(i,j)与(k,l)是同一位置，两条路径经过了相同的位置，即两条路径相交。而题目要求两条路径不能相交，因此这种情况是不合法的。
我们可以通过设状态值，让这种不合法的情况不影响状态转移方程的计算。
由于接下来要求的是路径上数值加和的最大值，我们可以将此时的状态值设为一个很小的值（如-INF，const int INF = 0x3f3f3f3f）。如此一来，不合法的状态一定不会在求其它状态时使用。

详细情况如下：
如果如果(i,j)与(k,l)是同一位置：
如果(i,j)与(k,l)都是(1,1)，那么 $dp_{i,j,k,l}$ 就是0。
如果(i,j)与(k,l)都是(m,n)，那么可以是

第一趟到达(m-1,n)后到达(m,n)，第二趟到达(m,n-1)后到达(m,n)，数字加和为 $dp_{i,j,k,l}=dp_{m-1,n,m,n-1}$
第一趟到达(m,n-1)后到达(m,n)，第二趟到达(m-1,n)后到达(m,n)，数字加和为 $dp_{i,j,k,l}=dp_{m,n-1,m-1,n}$
以上两种情况取最大值

对于其它情况，将状态设为一个很小的值， $dp_{i,j,k,l}=-INF$

如果(i,j)与(k,l)不是同一位置，或：

第一趟到达(i-1,j)后到达(i,j)，第二趟到达(k-1,l)后到达(k,l)，数字加和为 $dp_{i-1,j,k-1,l}+a_{i,j}+a_{k,l}$
第一趟到达(i,j-1)后到达(i,j)，第二趟到达(k-1,l)后到达(k,l)，数字加和为 $dp_{i-1,j,k,l-1}+a_{i,j}+a_{k,l}$
第一趟到达(i-1,j)后到达(i,j)，第二趟到达(k,l-1)后到达(k,l)，数字加和为 $dp_{i,j-1,k-1,l}+a_{i,j}+a_{k,l}$
第一趟到达(i,j-1)后到达(i,j)，第二趟到达(k,l-1)后到达(k,l)，数字加和为 $dp_{i,j-1,k,l-1}+a_{i,j}+a_{k,l}$
以上四种情况取最大值。

状态转移方程为：
$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}$

观察状态转移方程可知，由于要在这4个状态 $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}$ 中求最大值。
只有 $i = j 且 k = l$ 的状态 $dp_{i,j,k,l}$ 的值才是 $- I NF$ ，因此以上4个状态的值不可能都是 $- I NF$ 。
因此如果其中某一状态的值为 $- I NF$ ，则一定不会是数值最大的那个状态，不会影响 $dp_{i,j,k,l}$ 的计算结果。

观察该状态转移方程，在dp数组初值为0的情况下，当(i,j)与(k,l)都是(1,1)或(m,n)时，使用该状态转移方程也可以求出预期的值。

最终结果为第一趟从(1,1)到(m,n)，第二趟从(1,1)到(m,n)的路径上能获取的最大的数字加和，即 $dp_{m,n,m,n}$ 。

【题解代码】

写法1：符合上述基本概念的写法

#include<bits/stdc++.h>
using namespace std;
#define N 55
#define INF 0x3f3f3f3f
int m, n, a[N][N], dp[N][N][N][N];//dp[i][j][k][l]：第一趟传到(i,j)，第二趟传到(k,l)的所有路径中，权值加和最大的路径的权值加和 
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 i = 1; i <= m; ++i)for(int j = 1; j <= n; ++j)for(int k = 1; k <= m; ++k)for(int l = 1; l <= n; ++l){if(i == k && j == l){if(i == 1 && j == 1)dp[i][j][k][l] = 0;else if(i == m && j == n)dp[i][j][k][l] = max(dp[m-1][n][m][n-1], dp[m][n-1][m-1][n]);elsedp[i][j][k][l] = -INF;}elsedp[i][j][k][l] = max(max(dp[i-1][j][k-1][l], dp[i-1][j][k][l-1]), max(dp[i][j-1][k-1][l], dp[i][j-1][k][l-1]))+a[i][j]+a[k][l];}cout << dp[m][n][m][n];return 0;
}

写法2：使用状态转移方程求 $i = 1, j = 1$ 与 $i = m, j = n$ 的情况

#include<bits/stdc++.h>
using namespace std;
#define N 55
#define INF 0x3f3f3f3f
int m, n, a[N][N], dp[N][N][N][N];//dp[i][j][k][l]：第一趟传到(i,j)，第二趟传到(k,l)的所有路径中，权值加和最大的路径的权值加和 
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 i = 1; i <= m; ++i)for(int j = 1; j <= n; ++j)for(int k = 1; k <= m; ++k)for(int l = 1; l <= n; ++l){if(i == k && j == l && !(i == 1 && j == 1 || i == m && j == n))dp[i][j][k][l] = -INF;elsedp[i][j][k][l] = max(max(dp[i-1][j][k-1][l], dp[i-1][j][k][l-1]), max(dp[i][j-1][k-1][l], dp[i][j-1][k][l-1]))+a[i][j]+a[k][l];}cout << dp[m][n][m][n];return 0;
}