传纸条
题目 传纸条
思路分析
好题 当赏
再见
怎么可能放弃 (2024.3.5.22:00——2024.3.6.00:30 拿下！）
膜拜铅笔哥%%%
https://www.acwing.com/solution/content/51293/
y总视频讲错了
这题思路还是和上一题方格取数一样 都是把x1,y1 x2,y2 转变成n,x1,x2的状态表示
方格取数是从左上角出发两次到右下角 这题是左上角出发一次 右下角出发一次 可以把右下角往左上角走的那个情况调转一下方向 问题转变成上题一样的从左上角出发两次
还有一点不一样的是 之前是可以走重复的点 只不过只取一次的价值 这次变成了一定不能走重复的点 emm 但其实选出来的方案就是不会经过同一个点的 可以完全套用上题的写法
至于为什么最优解法不会经过同一个点（上题可以走重复实际也没走重复）
有以下证明：（看看得了）
情况一：最优解的两条路线是相互交叉经过的
则我们可以对交叉出来的部分进行路线交换，如下图的操作
于是，我们可以发现，所有的交叉路线都会映射成一种一条路线只在下方走，一条路线只在上方走的不交叉路线
因此我们只需集中解决情况二即可
情况二：最优解的两条路线不交叉，但在某些点有重合
由于方格取数，对于走到相同格子时，只会累加一次格子的价值
于是我们可以使用贪心中的微调法来进行这部分的证明
对于重合的格子，我们必然可以在两条路线中找到额外的一条或两条路线，使得新的路线不发生重合
具体参照下图：
由于原路线是最优解，则必然 wA=wB=0，则最优解路线必然是经过 A或 B的
因此，我们可以通过微调其中的一条路线，使之不经过重合点 C，同时路线的总价值没有减少
得证：最优解路线可以是不经过重复路线的
另外还有证明：
https://www.acwing.com/solution/content/12389/
en 反正意思就是这题模型变得和上一题一模一样了 就好像最低通行费和摘花生一样 多了一个可以往上和往左的选择 但是证明后根本不会往左走 只会往右下走 问题变成一模一样的情况
这里就是一个 从左上到右下 走两次 的最大价值的模型
（不能走同一位置或同一位置只能取一次）
证明部分可以不管 知道选出来的答案路径就是不会重复选同一个格子就行了
核心就是 使用f[n][x1][x2]这样的三维状态表示代替f[x1][y1][x2][y2]的四维表示
n表示横纵坐标之和 在走的过程中 同一时刻两条路径的n是相同的
前置问题解决了
就是dp分析了
状态表示 f[k][i][j]
集合：路径长度为k，第一条路线到i,k-i位置，第二条路线到j,k-j位置的所有方案
属性：MAX
用v表示当前位置需要累加的价值
当x1≠x2，当前两条路线走到的格子不是同一个，v=w(i,k−i)+w(j,k−j) 当x1=x2，当前两条路线走到了同一个格子中，只需要累加一次 v=w(i,k−i)
右右
下右
右下 下下
状态计算：f[k][i][j]=max({f[k-1][i][j],f[k-1][i-1][j],f[k-1][i][j-1],f[k-1][i-1][j-1]})+v;
这里有些乱 给一个理顺些的版本
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 55, M = 2 * N;
int n, m;
int w[N][N];
int f[M][N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++ i)
{
for (int j = 1; j <= m; ++ j)
{
cin >> w[i][j];
}
}
for (int k = 2; k <= n + m; ++ k)
{
for (int i = 1; i < k && i <= n; ++ i)
{
for (int j = 1; j < k && j <= n; ++ j)
{
int v = w[i][k - i];
if (i != j) //判断两条路线是否经过同一个格子 经过的话只需要累加一次
v += w[j][k - j];
f[k][i][j]=max({f[k-1][i][j],f[k-1][i-1][j],f[k-1][i][j-1],f[k-1][i-1][j-1]})+v;
}
}
}
cout << f[n + m][n][n] << endl;
return 0;
}
💬 评论