数字三角形
从集合角度来考虑$DP$问题
——闫氏DP分析法
原型
AcWing 898.数字三角形
详见算法基础课
例1
AcWing 1017.摘花生
分析
思路较为简单,不过多赘述
f[i][j]
代表走到(i, j)
点能获得的最大花生数量
状态转移方程为max(f[i - 1][j] + map[i][j], f[i][j - 1] + map[i][j])
代码(手打)
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
| #include<iostream> #include<cmath> #include<algorithm> #include<cstring>
using namespace std;
int map[110][110], f[110][110]; int t, r, c;
int main() { cin >> t; for(int i = 1; i <= t; i ++) { cin >> r >> c; for(int j = 1; j <= r; j ++) for(int k = 1; k <= c; k ++) cin >> map[j][k]; for(int j = 1; j <= r; j ++) for(int k = 1; k <= c; k ++) { f[j][k] += max(f[j - 1][k] + map[j][k], f[j][k - 1] + map[j][k]); } cout << f[r][c] << endl; memset(f, 0, sizeof(f)); memset(map, 0, sizeof(map)); } return 0; }
|
例2
AcWing 1018.最低通行费
这道题给我的启示:
做题之前一定要动脑
先看个错误案例
我的代码:
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
| #include<iostream> #include<cmath> #include<algorithm> #include<cstring> const int N = 1e2 + 10; using namespace std;
struct road { int t; int c; }f[N][N];
int map[N][N];
int main() { int n; cin >> n; int t = 2 * n - 1; for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) cin >> map[i][j]; for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) { if(f[i - 1][j].c + map[i][j] > f[i][j - 1].c + map[i][j]) { f[i][j].c = f[i][j - 1].c + map[i][j]; f[i][j].t = f[i][j - 1].t + 1; if(f[i][j].t == t && i != n && j != n) { f[i][j].c = f[i - 1][j].c + map[i][j]; f[i][j].t = f[i - 1][j].t + 1; if(f[i][j].t == t && i != n && j != n) f[i][j].c = 0x3f; } } if(f[i - 1][j].c + map[i][j] < f[i][j - 1].c + map[i][j]) { f[i][j].c = f[i - 1][j].c + map[i][j]; f[i][j].t = f[i - 1][j].t + 1; if(f[i][j].t == t && i != n && j != n) { f[i][j].c = f[i][j - 1].c + map[i][j]; f[i][j].t = f[i][j - 1].t + 1; if(f[i][j].t == t && i != n && j != n) f[i][j].c = 0x3f; } } if(f[i - 1][j].c == f[i][j - 1].c) { f[i][j].c = f[i - 1][j].c; f[i][j].t = min(f[i - 1][j].t, f[i][j - 1].t) + 1; if(f[i][j].t == t && i != n && j != n) f[i][j].c = 0x3f; } } cout << f[n][n].c;
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 37 38 39 40 41 42
| #include <iostream> #include <cstring>
using namespace std;
const int N = 110;
int n; int w[N][N]; int f[N][N];
int main() { cin >> n; for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= n; ++ j) { cin >> w[i][j]; } }
memset(f, 0x3f, sizeof f); f[1][1] = w[1][1];
for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= n; ++ j) { f[i][j] = min(f[i][j], f[i - 1][j] + w[i][j]); f[i][j] = min(f[i][j], f[i][j - 1] + w[i][j]); } }
cout << f[n][n] << endl;
return 0; }
|
很显然我做这道题没有经过思考,但是这种近似暴力的算法其实也是能AC的
个人认为,这种做法在考场上可以作为一种下下策,但是肯定会像今年T1一样重写一遍的
题目分析
这道题其实并不复杂,是一道基础的线性$DP$题目
这道题的切入点就是他的时间要求是2n - 1
,恰好和边长n
有一定的关系
时间就是经过的方格数,也就是说要求路径的曼哈顿距离是2n - 1
,我们可以注意到,这个恰好就是仅仅向右下走不向左上走的方法所需的曼哈顿距离
因此我们只需要考虑这道题目中“花费”这个变量,很容易求出简洁的状态转移方程,即f[i][j] = min(f[i - 1][j], f[i][j - 1]) + map[i][j];
最后就可以是简单的写代码过程啦~
例3
AcWing 1027.方格取数
题目分析
处理两个路线的走法
使用f[i1][j1][i2][j2]
表示分别走到(i1, j1)
,(i2, j2)
的状态
并且让两个点同时从(1, 1)
,(1, 1)
开始走
处理同一个格子不能被重复选择
只有在i1 + j1 == i2 + j2
时,两条路径的格子才可能重合
状态优化
根据(2),假设i1 + j1 = i2 + j2 = k
则可以使用f[k][i1][i2]
表示从(1, 1)
,(1, 1)
分别走到(i1, k - i1)
,(i2, k - i2)
路径的最大值
之所以使用这种表示方法是为了保证每个格子只能被走一次,因为此时两个点是在一个位置上的,因此可以保证不重复走一个格子
你以为这就完了吗?
孩子你还是太天真了
这道题有很多细节 导致我顺着思路改了一个多小时交了五次才AC
k
的遍历应该是从2
开始,因为1 + 1 = 2
起始点是(1, 1)
,恰好k
代表的是两者的和,因此当然是从2
开始啦
- 千万千万不要忘了判
i1
和i2
的关系,如果二者相等意味着两者的坐标相等,也就是说此时只能加一次这个格子的数
- 在遍历两者的时候,加一条判断
j1
和j2
的语句,因为可能会出现k - i
越界的情况,所以务必要判断!!!
核心代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| for(int k = 2; k <= n * 2; k ++) { for(int i1 = 1; i1 <= n; i1 ++) { for(int i2 = 1; i2 <= n; i2 ++) {
if(k - i1 <= 0 || k - i1 > n || k - i2 <= 0 || k - i2 > n) continue; if(i1 == i2) { f[k][i1][i2] = max(f[k - 1][i1][i2], f[k - 1][i1 - 1][i2], f[k - 1][i1][i2 - 1], f[k - 1][i1 - 1][i2 - 1]) + map[i1][k - i1]; continue; } f[k][i1][i2] = max(f[k - 1][i1][i2], f[k - 1][i1 - 1][i2], f[k - 1][i1][i2 - 1], f[k - 1][i1 - 1][i2 - 1]) + map[i1][k - i1] + map[i2][k - i2]; } } }
|
例4
AcWing 275.传纸条
这道题不能说跟例3相似,只能说完全一样
按照例三思路分析,只需要将k
的循环中的n * 2
改成x + y
即可
直接上代码了
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 37 38 39 40 41 42 43
| #include<iostream> #include<cmath> #include<algorithm> #include<cstring>
const int N = 55;
using namespace std;
int x, y; int f[N * 2][N][N], map[N][N];
inline short max(int a, int b, int c, int d) { int tmp = max(a, b); tmp = max(tmp, c); return max(tmp, d); }
int main() { cin >> x >> y; for(int i = 1; i <= x; i ++) for(int j = 1; j <= y; j ++) cin >> map[i][j];
for(int k = 1; k <= x + y; k ++) for(int i1 = 1; i1 <= x; i1 ++) for(int i2 = 1; i2 <= x; i2 ++) { if(k - i1 <= 0 || k - i1 > y || k - i2 <= 0 || k - i2 > y) continue; if(i1 == i2) { f[k][i1][i2] = max(f[k - 1][i1][i2], f[k - 1][i1 - 1][i2], f[k - 1][i1][i2 - 1], f[k - 1][i1 - 1][i2 - 1]) + map[i1][k - i1]; continue; } f[k][i1][i2] = max(f[k - 1][i1][i2], f[k - 1][i1 - 1][i2], f[k - 1][i1][i2 - 1], f[k - 1][i1 - 1][i2 - 1]) + map[i1][k - i1] + map[i2][k - i2]; }
cout << f[x + y][x][x];
return 0; }
|