ACDaily 5

本文最后更新于:3 个月前

从集合角度分析DP问题

算法特点

  • 一般问法:最值(价值等属性)、达到某一目标的方向总数

  • 背包问题的本质为组合问题,即在一定条件下从一部分物品中挑选物品;同时也类似于图论的最短路,可以说,DP是一种特殊的图论

  • 暴力做法:方案数量为指数级

  • 化零为整:挖掘不同方案间的共同关系,把有相同关系的元素放在一起

  • 化整为零:把一个集合划分为多个子集,进行分析

  • 解决问题的过程中一定抓住从实际含义出发

具体的分析在下述例题中会有解释

题解的优化可以参考ACDaily 4

01背包

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。

本题题解具体优化可以参考ACDaily 4,此处借此例讲解动态规划基本的算法架构

算法架构:动态规划集合化

  1. 状态表示(一般为二维,不可能超时)f[i][j]

    • 集合的思想,f[i][j]表示的并非是j体积背包下对前i个物品进行选择下的价值最大值,而是j体积下对前i个物品进行选择下的所有方案的最大价值(每个物品可选可不选)
    • 属性:min、max、count,即数组中的元素表示最值或方案数
  2. 状态计算(化零为整)

    1. 集合的划分,划分依据:最后一个不同点。即在限制条件下(确定问题域),按选或不选第i个物品(i个物品中的最后物品)对方案进行划分为A(选i)和B(不选i)集合
      • 要求:不重不漏,每个子集中的元素具有相同共性(都选或没选第i个物品),各子集又能组合成全集
    2. 对不选i的集合中(B)所有方案的最大价值进行计算,得到max1
    3. 按物品选择是否发生变化,对上述划分包含选择第i个物品的方案(即A方案集合)进行分区,物品i所在区域为不变区,前i-1个物品组成的区域为变化区
    4. 寻找变化区中总价值最大的物品选择方案,加上第i个物品的价值,得到最大价值max2
    5. max(max1, max2),得到整体最大价值

    关键在于选择划分方式,例如以下的摘花生与最大子序列长度

1. 摘花生

Hello Kitty想摘点花生送给她喜欢的米老鼠。

她来到一片有网格状道路的矩形花生地(如下图),从西北角进去,东南角出来。

地里每个道路的交叉点上都有种着一株花生苗,上面有若干颗花生,经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty只能向东或向南走,不能向西或向北走。

问Hello Kitty最多能够摘到多少颗花生。

输入格式

第一行是一个整数T,代表一共有多少组数据。

接下来是T组数据。

每组数据的第一行是两个整数,分别代表花生苗的行数R和列数 C。

每组数据的接下来R行数据,从北向南依次描述每行花生苗的情况。每行数据有C个整数,按从西向东的顺序描述了该行每株花生苗上的花生数目M。

输出格式

对每组输入数据,输出一行,内容为Hello Kitty能摘到得最多的花生颗数。

数据范围

1≤T≤100,
1≤R,C≤100,
0≤M≤1000

输入样例:

2
2 2
1 1
3 4
2 3
2 3 4
1 6 5

输出样例:

8
16

题解:

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 55, MOD = 1000000007;
int w[N][N];
int f[N][N][13][14];

int main()
{
int n, m, k;
cin >> n >> m >> k;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
cin >> w[i][j];
w[i][j]++; // 调整整体价值范围
}

f[1][1][0][0] = 1;
f[1][1][1][w[1][1]] = 1; // 初始化

for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
if(i == 1 && j == 1) continue; // 起点已进行过初始化
for(int u = 0; u <= k; u++)
for(int v = 0; v <= 13; v++)
{
int &val = f[i][j][u][v];
val = (val + f[i-1][j][u][v]) % MOD;
val = (val + f[i][j-1][u][v]) % MOD;

if(u > 0 && v == w[i][j])
{
for(int c = 0; c < v; c++)
{
val = (val + f[i-1][j][u-1][c]) % MOD;
val = (val + f[i][j-1][u-1][c]) % MOD;
}

}
}
}

int res = 0;
for(int c = 0; c <= 13; c++) res = (res + f[n][m][k][c]) % MOD;

cout << res << endl;
return 0;
}

2. 最长上升子序列

给定一个长度为 N 的数列,求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 N。

第二行包含 N 个整数,表示完整序列。

输出格式

输出一个整数,表示最大长度。

数据范围

1≤N≤1000,
−109≤数列中的数≤109

输入样例:

7
3 1 2 1 8 5 6

输出样例:

4

题解:

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
#include <iostream>

using namespace std;

const int N = 1010;

int n;
int w[N], f[N];

int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> w[i];

int mx = 1; // 找出所计算的f[i]之中的最大值,边算边找
for (int i = n; i >= 0; i--) {
f[i] = 1; // 设f[i]默认为1,找不到前面数字小于自己的时候就为1
for (int j = i+1; j < n; j++) {
if (w[i] < w[j]) f[i] = max(f[i], f[j] + 1); // 这种写法是f[j]已经更新过的正常写法
}
mx = max(mx, f[i]);
}

cout << mx << endl;
return 0;
}

3. 地宫寻宝

X 国王有一个地宫宝库,是 n×m 个格子的矩阵,每个格子放一件宝贝,每个宝贝贴着价值标签。

地宫的入口在左上角,出口在右下角。

小明被带到地宫的入口,国王要求他只能向右或向下行走。

走过某个格子时,如果那个格子中的宝贝价值比小明手中任意宝贝价值都大,小明就可以拿起它(当然,也可以不拿)。

当小明走到出口时,如果他手中的宝贝恰好是 k 件,则这些宝贝就可以送给小明。

请你帮小明算一算,在给定的局面下,他有多少种不同的行动方案能获得这 k 件宝贝。

输入格式

第一行 3 个整数,n,m,k,含义见题目描述。

接下来 n 行,每行有 m 个整数 Ci 用来描述宝库矩阵每个格子的宝贝价值。

输出格式

输出一个整数,表示正好取 k 个宝贝的行动方案数。

该数字可能很大,输出它对 1000000007 取模的结果。

数据范围

1≤n,m≤50,
1≤k≤12,
0≤Ci≤12

输入样例1:

2 2 2
1 2
2 1

输出样例1:

2

输入样例2:

2 3 2
1 2 3
2 1 5

输出样例2:

14

题解:

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 55, MOD = 1000000007;
int w[N][N];
int f[N][N][13][14];

int main()
{
int n, m, k;
cin >> n >> m >> k;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
cin >> w[i][j];
w[i][j]++; // 调整整体价值范围
}

f[1][1][0][0] = 1;
f[1][1][1][w[1][1]] = 1; // 初始化

for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
if(i == 1 && j == 1) continue; // 起点已进行过初始化
for(int u = 0; u <= k; u++)
for(int v = 0; v <= 13; v++)
{
int &val = f[i][j][u][v];
val = (val + f[i-1][j][u][v]) % MOD;
val = (val + f[i][j-1][u][v]) % MOD;

if(u > 0 && v == w[i][j])
{
for(int c = 0; c < v; c++)
{
val = (val + f[i-1][j][u-1][c]) % MOD;
val = (val + f[i][j-1][u-1][c]) % MOD;
}

}
}
}

int res = 0;
for(int c = 0; c <= 13; c++) res = (res + f[n][m][k][c]) % MOD;

cout << res << endl;
return 0;
}

本文作者: waitingFor
本文链接: http://example.com/2022/03/05/ACDaily/ACDaily-5/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!