DP. 数字三角形模型

DP.数字三角形模型

• • 1015. 摘花生
  • 1018. 最低通行费
  • 1027. 方格取数
  • 275. 传纸条

 

---

1015. 摘花生

终点：

• 东南角 $(i,j)$
• 设东南角最大花生数 dp[i][j]

那 dp[i][j]，从哪里来？

• 可能一：左边 dp[i-1][j]
• 可能二：上边 dp[i][j-1]
• 转移方程：$dp[i][j]=max(dp[i-1][j]+w[i][j],dp[i][j-1]+w[i][j])$
• 最简单的情况：$dp[0][0]=0$

第 i 层的答案只依赖于第 i 层和第 i - 1 层，可以状态压缩。

• 转移方程：$f[j]=max(f[j],f[j-1])+w$
   

---

1018. 最低通行费

因为从方格左上角走到右下角的距离是：N*N，要在 2N-1 的时间出去，这代表不能走回头路。

在这个限定条件下，整体思路\代码和摘花生没有区别。
 

---

1027. 方格取数

一开始的思路就是，俩次 DP 即可。

但是分开走的局部最优，不是全局最优。

从 A 点到 B 点共走了两次，我们可以设两条路径是同时出发的。

因为是俩条路径，我们用俩维数组是存不下的，我们开四维的。

走法还是不能走回头路，俩个方向 * 俩个走法 = 4。

如何处理同一格子不能被重复选择？

• a = c 且 b = d

按照题目要求，需要在刷新值，第一次走过的格子要变成 0。

for (int a = 1; a < n; a++) 
	for (int b = 1; b < n; b++) 
		for (int c = 1; c < n; c++) 
			for (int d = 1; d < n; d++) {
				int x = max(f[a - 1][b][c - 1][d], f[a - 1][b][c][d - 1]);      
				// 从上边、上边来，从上边、左边来
				int y = max(f[a][b - 1][c - 1][d], f[a][b - 1][c][d - 1]);      
				// 从左边、上边来，从左边、左边来
				int z = g[a][b] + ((a == c && b == d) ? 0 : g[c][d]); 
				// 是否走同一个格子，同一个格子只能走一次，走第二次赋值为 0 
				f[a][b][c][d] = max(x, y) + z;
             }
	return f[n - 1][n - 1][n - 1][n - 1];
1
2
3
4
5
6
7
8
9
10
11
12
13

我们优化一下，如何处理同一格子不能被重复选择？

• 俩者总步数相同才有可能走到同一格子，a + b = c + d

虽然有四个状态，但因为有一个等价关系，我们可以优化成三个状态。

• b = k - a，d = k - c
• f[k][a][c]：表示所有从 (1,1) (1,1) 分别走到 (a, k-a)，(c, k-c) 的路径最大值

#include 
using namespace std;

const int N = 15;
int n;
int w[N][N], f[N*2][N][N];

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 <= 2*n; k++) {  
    // i和j都是从1开始的，而k==i+j，所以k从2开始
        for(int i1 = 1; i1 <= n; i1++) {
            for(int i2 = 1; i2 <= n; i2++) {
                int j1 = k-i1, j2 = k-i2;
                if(j1>=1 && j1<=n && j2>=1 && j2<=n) {
                    // 不能越界
                    int &x = f[k][i1][i2];
                    int t = w[i1][j1];
                    if(i1!=i2) t += w[i2][j2];
                    // 不重合则需要加两个权重.
                    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[n*2][n][n] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

 

---

275. 传纸条

从小渊传到小轩的纸条只可以向下或者向右传递，小轩传给小渊的纸条只可以向上或者向左传递。

可是这并不影响结果，因为任意一个从点 $(m,n)$ 到点 $(1,1)$ 的路径都可以映射成一个从点 $(1,1)$ 到点 $(m,n)$ 的路径。

这样就和方格取数相同了。

与方格取数不同的是, 一个方格只能经过一次（每个同学只帮一次）。