数字三角形
从集合角度来考虑$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;
}
|
