Acwing算法提高课-DP-数字三角形模型
摘花生
见另一篇文章：
最低通行费
类似于上面的摘花生，不过摘花生求的是集合的MAX，最低通行费求的是集合的MIN。
但是，由于数组初始化为0。不能像摘花生一样简单的max()。
最后一步，可能是从上方走来的，也可能是从左方走来的。
对于除第一行和第一列的元素来说，确实可以用min(上来，左来)求较小值。
但对于处理边界元第一行和第一列时，以第一行为例：
- 从上方结果是
0。通行费大于一，min的值一定是0。
可不可以加一个特判呢？
- 第一行的时候，当前位置的值等于左来方式的值。
- 第一列的时候，当前位置的值等域上来方式的值。
- 其余情况，当前位置的值等于两种方式中的较小值。
思路比较清晰，但写起来其实挺麻烦的。下面是另一种写法，用一个新的表，增加了空间，但简化了写法。
- 状态表示：
f[i][j]左上角走到第i行第j列的最低通行费。 - 集合属性：
MIN - 状态计算：最后一步划分为从左来和从上来。
#include"bits/stdc++.h"
using namespace std;
int N;
int w[110][110];
int dp[110][110];
int main() {
cin >> N;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
scanf("%d", &w[i][j]);
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i == 1 && j == 1)dp[i][j] = w[i][j];
else {
dp[i][j] = 1e9;
if (i > 1)dp[i][j] = min(dp[i][j], dp[i - 1][j] + w[i][j]);
if (j > 1)dp[i][j] = min(dp[i][j], dp[i][j - 1] + w[i][j]);
}
}
}
printf("%d\n", dp[N][N]);
return 0;
}上面代码的思路是特判左上角。 只有不在第一行的时候，才可以从上面过来。 只有不再第一列的时候，才可以从左边过来。
方格取数
摘花生中，只走一次的情况：
f[i][j]表示所有从(1,1)到(i,j)的路径的最大值。f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j]
走两次：
f[i1][j1][i2][j2]表示所有从(1,1),(1,1)分别走到(i1,j1),(i2,j2)的路径的最大值。
如何处理“同一格子不能被重复选择”：
- 只有在
i1+j1==i2+j2时，两条路径的格子才可能重合
状态表示：f[k][i1][i2]表示所有从(1,1),(1,1)分别走到(i,k-i1),(i2,k-i2)的路径的最大值。
k表示两条路线当前走过的格子的横纵坐标之和。
k=i1+j1=i2+j2
属性：MAX
状态计算：f[k][i1][i2]=max(f[k - 1][i1 - 1][i2 - 1],f[k - 1][i1 - 1][i2],f[k - 1][i1][i2 - 1],f[k - 1][i1][i2])+t
- 最后一步的第一条路线可以从上来、左来：
max(f[k - 1][i1-1][*],f[k - 1][i1][*]) - 最后一步的第二条路线可以从上来、左来：
max(f[k - 1][*][i2-1],f[k - 1][*][i2])
#include"bits/stdc++.h"
using namespace std;
int n;
int w[15][15];
int f[30][15][15];
int main() {
cin >> n;
int a, b, c;
while (cin >> a >> b >> c, a || b || c)w[a][b] = c;
for (int k = 2; k <= n + n; k++) {
for (int i1 = 1; i1 <= n; i1++) {
for (int i2 = 1; i2 <= n; i2++) {
int j1 = k - i1, j2 = k - i2;
if (j1 >= 1 && i1 <= n && j2 >= 1 && j2 <= n) {
int t = w[i1][j1];
if (i1 != i2)t += w[i2][j2];
int &x = f[k][i1][i2];
x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
x = max(x, f[k - 1][i1 - 1][i2] + t);
x = max(x, f[k - 1][i1][i2 - 1] + t);
x = max(x, f[k - 1][i1][i2] + t);
}
}
}
}
cout << f[2 * n][n][n];
return 0;
}在while中，判断结束的方法是,后位操作。
传纸条
状态表示f[k][x1][x2]：所有第一条从(1,1)走到(x1,k-x1)和第二条从(1,1)走到(x2,k-x2)的路线的最大好心程度之和。
属性：MAX
状态计算：
- 最后一步的两条路线分别有两种来法：从上来、从左来。
- 最后一步的位置可能相同：
t = w[x1][k - x1] - 最后一步的位置可能不同：
t = w[x1][k - x1] + w[x2][k - x2]
#include"bits/stdc++.h"
using namespace std;
int n, m;
int w[55][55];
int f[110][55][55];
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 <= m + n; k++) {
for (int x1 = max(1, k - m); x1 <= min(k - 1, n); x1++) {
for (int x2 = max(1, k - m); x2 <= min(k - 1, n); x2++) {
int t = w[x1][k - x1];
if (x2 != x1)t += w[x2][k - x2];
for (int a = 0; a <= 1; a++)
for (int b = 0; b <= 1; b++)
f[k][x1][x2] = max(f[k][x1][x2], f[k - 1][x1 - a][x2 - b] + t);
}
}
}
cout << f[n + m][n][n] << endl;
return 0;
}传纸条在dp阶段的代码跟方格取数是一样的。
这是因为，当两条路径相交时，这个点加的值就是0+w[i][j]。
如果选择让其中一条路径绕过这个点的话，加值就是w[i][j-1]+w[i][j]或w[i-1][j]+w[i][j]。
因为是非负数，所以绕路的情况一定优于有相交点的情况，有相交点的路径一定不是最优解。
不论是在方格取数中，还是在传纸条中，最优解永远不会由两段相交的路径组成。