动态习题集

众所周知，动态规划问题的训练不但需要学习其精巧的思维还需要大量练习积累经验，才能较好地掌握这一方面的知识。所以这篇文章就当作记录一些我所收集到的经典的动态规划问题的习题集。

显然这个习题集的体系逐渐完善体量也越来越大，所以请善用目录。

本集初建于2022年1月1日将持续更新。

动态规划（Dynamic Programming， DP）是一种将原问题分解成结构相似规模更小的子问题的进行递推处理的求解复杂问题的有力算法。但是动态规划并不是指某一种特定解法的算法而是一种复杂问题简单化的思路，针对这种思路可以考察到的问题形式和种类非常丰富非常考验解题人的思维~

动态规划问题的要素：

  1. 最优子结构：从子问题的最优解可以推出更大规模的问题的最优解的问题结构就满足最优子结构的特点，对于这样的问题你可以假定不必知道子问题具体是如何获得的，只需由已知的最优子解就可得到更大规模的最优解即子问题间相互独立
  2. 重叠子问题：从最小子问题递推（递归）地重复求解能得到最优解就一定要满足子问题与原问题只是规模上的差别在计算方法需要是一致的而不能在解决子问题的时候生成新的子问题，这样就能通过子问题的解重构出原问题的解了

线性DP & 数字三角形模型

摘花生

题面描述：Hello Kitty 想摘点花生送给她喜欢的米老鼠。她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。Hello Kitty只能向东或向南走，不能向西或向北走。问Hello Kitty 最多能够摘到多少颗花生。

1.gif

原题链接：AcWing 1015. 摘花生

方法：复杂度 On2O_{n^2}

状态表示：

  1. 数组结构：与原花生地矩阵大小相同的矩阵
  2. 位置信息：从起始点走到当前位置代表的点
  3. 数值信息：从起始点走到当前位置代表的点所获得的最大花生数

状态计算：

  1. 考虑到每一种状态只能从它的北面或西面转移过来，故得到状态转移方程f[i][j] = max(f[i-1][j], f[i][j-1]) + w[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
32
#include<iostream>
#include<cstdio>
using namespace std;

const int N = 110;

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

int main(){
    int T;
    cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i = 1; i <=  n; i++){
            for(int j = 1; j <= m; j++){
                scanf("%d", &w[i][j]);
            }
        }
        
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                f[i][j] = max(f[i-1][j], f[i][j-1]) + w[i][j];
            }
        }
        
        cout<<f[n][m]<<endl;
    }
    
    return 0;
}

最低通行费

题面描述：大意是给定一个 n×nn\times n 的矩阵，让我们从左上角出发，最终走到右下角，要求走过的方块数量的不能超过 2n−1 个并且每走到一个方格都需要加上一定的价值w，求所有路线中经过的方块的总价值最少的路线

原题链接：AcWing 1018. 最低通行费

方法：复杂度 On2O_{n^2}

经过分析可以得到商人不能走过超过 2n-1 个方格并且需要从起点走到终点，故商人只能每次往下或往右走，只需要注意一下要求的是最小值然后应用上一题的思路即可。

完整代码：

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<cstdio>
#include<cstring>
using namespace std;

const int N = 110, INF = 1e9;
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++){
            scanf("%d", &w[i][j]);
        }
    }
    
    //初始化的方式
    memset(f, 0x3f, sizeof f);
    f[0][1] = f[1][0] = 0;
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            f[i][j] = min(f[i-1][j], f[i][j-1])+w[i][j];
        }
    }
    
    // //或者特判处理
    // for(int i = 1; i <= n; i++){
    //     for(int j = 1; j <= n; j++){
    //         if(i == 1 && j == 1) f[i][j] = w[i][j];
    //         else{
    //             f[i][j] = INF;
    //             if(i > 1) f[i][j] = min(f[i][j], f[i-1][j] + w[i][j]);
    //             if(j > 1) f[i][j] = min(f[i][j], f[i][j-1] + w[i][j]);
    //         }
    //     }
    // }
    
    cout<<f[n][n];
    return 0;
}

方格取数

题面描述：设有 N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。如下图所示：

2.gif

某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。

在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。

此人从 A 点到 B 点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。

原题链接：AcWing 1027. 方格取数

备用链接：洛谷 P1004 NOIP2000 提高组 方格取数

方法：复杂度 On3O_{n^3}

状态表示：

  1. 数组结构：一维大小为 2n-1 另外两维大小都为 n 的三维矩阵

  2. 位置信息：第一维表示当前两位同时出发的小盆友走过的格子数（两个人走过的格子数相同，这里为了计算简便就直接使用格子的坐标和表示）第二维和第三维都表示当前小盆友在横轴上走过的格子数

    对于表示两个小盆友在矩阵上面各自的位置状态应该是需要用四维（ i1, j1, i2, j2i_1, \ j_1,\ i_2,\ j_2 ）但是我们经过分析可以得到只有当两个小盆友走过相同的方格数是才可能碰到一起，即同时取到了同一个数（不能）故我们另外设置一维表示当前走过的路程（时间），然后其他两维就可以用两位小盆友走过的任意一轴的距离去表示

  3. 数值信息：表示两位小盆友从起点走到其各自的位点能获得的最大总数值

状态转移：

  1. 由上面的分析我们可以得到，两个小盆友的都各自有两种转移的方案即向右行和向下行故组合得到四种转移方案故转移方程为 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])+tf[k][i_1][i_2] = \max{(f[k-1][i_1-1][i_2-1],\ f[k-1][i_1-1][i_2],\ f[k-1][i_1][i_2-1],\ f[k-1][i_1][i_2]) + t} 其中 tt 表示两位小盆友到达当前位点所能获得的数字和（需要判断是否重合）

完整代码：

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
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

const int N = 15;

int n;
int w[N][N];
int 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 <= 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 || j1 > n || j2 < 1 || j2 > n) continue;
                
                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[n+n][n][n];
    return 0;
}

最长不下降子序列（LIS）

题面描述：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

原题链接：Leetcode300. 最长上升子序列

方法1：复杂度 On2O_{n^2}

状态表示：

  1. 数组结构：与原数组长度相同的一维数组表示
  2. 位置信息：从该位置开始（一定含有这个元素）往前扩展的子序列
  3. 数值信息：子序列的最大长度

状态计算：

  1. 转移方程： dp[i]=max(dp[j])+1 ,其中0⩽j<i 且num[j]<num[i]dp[i] = max(dp[j])+1\ , 其中0\leqslant j < i\ 且num[j]<num[i]

完整代码：

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
#include<cstdio>
#include<iostream>
using namespace std;

const int N = 1010;
int a[N], f[N], n;

int main(){
    cin>>n;
    
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    
    for(int i = 1; i <= n; i++){
        f[i] = 1;
        for(int j = 1; j < i; j++){
            if(a[j] < a[i])
               f[i] = max(f[i], f[j]+1);
        }
    }
    
    int ans = 0;
    
    for(int i = 1; i <= n; i++) ans = max(ans, f[i]);
    cout<<ans;
    return 0;
}

该方法由于其数值信息非常符合直觉上的第一选择梯队（与要求项属性相同）故相对容易理解和想到但相对的复杂度较高。

方法2：复杂度 Onlog⁡nO_{n\log_n}

状态表示：

  1. 数组结构：与原数组长度相同的一维数组表示
  2. 位置信息：表示子序列的长度
  3. 数值信息：表示长度为下标所示长度的子序列的结尾元素的最小值

状态计算：

  1. 如果 num[i] > d[len] 则将其直接加到数组d的末尾并更新最长长度len++
  2. 否则，在d数组中进行二分查找，找到比 num[i] 小的最大 d[k] (二分查找) 并更新 d[k+1] = num[i]
  3. 以上可以总结找到第一个大于 num[i] 的最小 d[k] 然后更新 d[k]=num[i] （前提将dp数组初始化为无穷）

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 100010, INF = 0x3f3f3f3f;

int dp[N], a[N];

int main(){
    memset(dp, 0x3f, sizeof dp);
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        int t;
        scanf("%d", &t);
        * lower_bound(dp, dp+n, t) = t;
    }
    int ans = 0;
    while(dp[ans]!=INF) ans++;
    cout<<ans;
    return 0;
}

注意：如果是求最长不下降子序列的话是查找到第一个大于 num[i] 的数，但如果是要求最大递增子序列的话就需要查找到第一个不小于 num[i] 的数（相等时不替换）即将upper_bound() 替换为 lower_bound()

这种方法精巧就精巧在动态维护dp数组时数组时自维护有序的，这样就可以使用二分的方法优化查找过程降低复杂度了（准确来讲这种方式并不是正统的dp更偏向于二分）

怪盗基德的滑翔翼

题面描述：给定一个长度为 n 的一维数组 w[n]，表示每个楼房的高度。怪盗基德可以选定任意一个楼房，作为他的起始位置。他可以选择向左或向右出发直到边界，途中不能改变方向。题目要求我们找出一条路径，使得他飞行的路线上，经过的高度递减的楼房子序列长度最大

输出该子序列的长度

原题链接：AcWing 1017. 怪盗基德的滑翔翼

方法： On2O_{n^2} 或 Onlog⁡nO_{n\log_{n}}

本题就是最长上升子序列的简单应用正向求一遍然后反向求一遍最长上升子序列即可，解答代码使用的是朴素的 On2O_{n^2} 的做法优化版读者可自行参考练习

完整代码：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 110;
int n;
int a[N], f[N];

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        
        //正向
        int ans = 0;
        for(int i = 1; i <= n; i++){
            f[i] = 1;
            for(int j = 1; j < i; j++){
                if(a[i] > a[j]) f[i] = max(f[i], f[j]+1);
            }
            ans = max(ans, f[i]);
        }
            //反向
        for(int i = n; i; i--){
            f[i] = 1;
            for(int j = n; j > i; j--){
                if(a[i] > a[j]) f[i] = max(f[i], f[j]+1);
            }
            ans = max(ans, f[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

登山

题面描述：题目给定一个长度为 n 的数组 a[n]，表示某个景点的海拔高度；观光队从起点出发，初始海拔高度为 0，先上山后下山，且开始下山后不再往上走

让我们找出一个方案，使得观光队浏览到的景点数量最多

原题链接：AcWing 1014. 登山

方法： O(n2)O_{(n^2)} 或 O(nlog⁡n)O_{(n\log_{n})}

本题同样是将最长上升子序列的一个扩展应用，分别计算以一个点为顶点的上升和下降子序列的长度和取最大即可

完整代码：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 1010;
int n;
int a[N], f1[N], f2[N];

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    
    for(int i = 1; i <= n; i++){
        f1[i] = 1;
        for(int j = 1; j < i; j++){
            if(a[i] > a[j]) f1[i] = max(f1[i], f1[j]+1);
        }
    }
    
    for(int i = n; i; i--){
        f2[i] = 1;
        for(int j = n; j > i; j--){
            if(a[i] > a[j]) f2[i] = max(f2[i], f2[j]+1);
        }
    }
    
    int ans = 0;
    for(int i = 1; i <= n; i++) ans = max(ans, f1[i]+f2[i]-1);
    cout<<ans;
    return 0;
}

合唱队形

题面描述：给定一个长度为 n 的数组 a[n]，表示第 i 位同学的身高为 a[i]，题目要求我们从这个数组中删去一些小朋友，使得最终身高的顺序是先递增后递减；

问最少删除多少个小朋友，可以构成想要的先递增后递减的序列

原题链接：AcWing 482. 合唱队形

方法： O(n2)O_{(n^2)} 或 O(nlog⁡n)O_{(n\log_{n})}

本题为上一题登山的变形题，解法基本一致就直接贴解题代码

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 110;
int n;
int a[N], f1[N], f2[N];

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    
    for(int i = 1; i <= n; i++){
        f1[i] = 1;
        for(int j = 1; j < i; j++){
            if(a[i] > a[j]) f1[i] = max(f1[i], f1[j]+1);
        }
    }
    
    for(int i = n; i; i--){
        f2[i] = 1;
        for(int j = n; j > i; j--){
            if(a[i] > a[j]) f2[i] = max(f2[i], f2[j]+1);
        }
    }
    
    int ans = 0;
    for(int i = 1; i <= n; i++) ans = max(ans, f1[i]+f2[i]-1);
    cout<<n-ans;
    return 0;
}

友好城市

题面描述：Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。

北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。

每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。

编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。

原题链接：AcWing 1012. 友好城市

方法： On2O_{n^2} 或 Onlog⁡nO_{n\log_{n}}

首先我们考虑什么情况下两条航线会发生相交：

友好城市示意图

为了便于区分我们以北岸的节点从左往右看（也就是以北岸的坐标从小到大）我们可以清楚地看到，当北岸的坐标是从小到大是顺序分析时如果南岸的坐标是从大到小的话那么这两条航线就是相交的

也就是以北岸节点坐标从小到大排序得到的对应南岸节点坐标序列必须也是从小到大的顺序的，否则就会出现相交的航线。

由此，我们构建出来了基本的解题思路：将北岸节点坐标从小到大排序得到对应的南岸的坐标序列，在这样构造出来的序列总找最长连续不下降子序列（或者称为最长连续上升子序列即可，因为不同城市的友好城市不相同）

完整代码：

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 5010;
pair<int, int> a[N];
int n;
int f[N];

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++) scanf("%d%d", &a[i].first, &a[i].second);
    sort(a+1, a+n+1);
    
    int ans = 0;
    for(int i = 1; i <= n; i++){
        f[i] = 1;
        for(int j = 1; j < i; j++){
            if(a[i].second > a[j].second) f[i] = max(f[i], f[j]+1);
        }
        ans = max(ans, f[i]);
    }
    
    cout<<ans;
    return 0;
}

最大上升子序列和

题面描述：本题定义了一个上升子序列和：对于元素满足从左往右数值递增的次序的子序列的和。我们要求出该序列中最大上升子序列和。

原题链接：AcWing 1016. 最大上升子序列和

方法： O(n2)O_{(n^2)}

本题无非就是将简单的最长连续不下降子序列上进行了些许改进，通过观察我们可以发现这题与原版只是在所求出的值上有些许不同，而转移的性质几乎是一致的。

所以，我们只需要在朴素版求最长上升子序列的解法上将DP数组委会的数值信息改成最长上升子序列和而转移的调节也相应进行微调即可

完整代码：

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>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 1010;
int n;
int a[N], f[N];

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    
    int ans = 0;
    for(int i = 1; i <= n; i++){
        f[i] = a[i];
        for(int j = 1; j < i; j++){
            if(a[i] > a[j]) f[i] = max(f[i], f[j]+a[i]);
        }
        ans = max(ans, f[i]);
    }
    cout<<ans;
    return 0;
}

拦截导弹

题面描述：本题给定一个数组 a[N]，让我们求解两个量：1. 该数组的最长不上升子序列； 2. 该数组最少能被几个不上升子序列全部覆盖

原题链接：AcWing 1010. 拦截导弹

备用链接：洛谷 P1020 NOIP1999 普及组 导弹拦截

方法1：O(n2)O_{(n^2)}

第一问无非就是最长不上升子序列，所以这里关注第二问求至少需要多少个不上升子序列能覆盖全部序列。

求第二问的思路继承自 Onlog⁡nO_{n\log{n}} 的最长上升子序列的思路，也即贪心的思路：现在考虑前 i−1i-1 个数已经通过贪心的得到最优解（有点像DP的前提）即所有前 i−1i-1 个数已经构成了 kk 个不上升子序列组，由于我们只关注子序列组中的最后一个元素的大小，所以我们用最后一个元素代表这个不下降子序列组

现在考虑第 ii​​ 个数的放置方案，若这个数能够接到现存的 kk​​ 个不下降子序列中也即第 ii​​ 个数比这 kk​​ 组子序列结尾的某个数要小，则将第 ii​​ 个数可以接到其后，这里贪心地处理将第 ii​​ 个数作为 “最小的不比第 ii​​ 个数小的数结尾的子序列” 的新结尾元素；若不存在则意味着这个数无法作为结尾也就是这个数需要新添一组

完整代码：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 1010;

int n;
int q[N];
int f[N], g[N];

int main(){
    while(cin>>q[n])n++;
    
    int ans = 0;
    for(int i = 0; i < n; i++){
        f[i] = 1;
        for(int j = 0; j < i; j++){
            if(q[j] >= q[i]) f[i] = max(f[i], f[j]+1);
        }
        ans = max(ans, f[i]);
    }
    
    cout<<ans<<endl;
    
    int cnt = 0;
    for(int i = 0; i < n; i++){
        int k = 0;
        while(k < cnt && g[k] < q[i]) k++;
        g[k] = q[i];
        if(k >= cnt) cnt++;
    }
    
    cout<<cnt<<endl;
    return 0;
}

方法2：O(nlog⁡n)O_{(n\log{n})}

这个思想与贪心求最长不下降子序列很相似，这里可以注意到这实际上是会自然构成一个升序序列的，也就是在查找时可以用二分优化处理;

这里要注意的是，第一问要求最长的序列长度也就是当高度相等时需要更新数据（多占一个位）以使得获得的序列长度最长所以需要更新时需要使用upper_bound()，再则由于二分法只适于求“上升子序列”故这里需要倒序求；对于第二问而言则需要把相同高度的数分到同一组以使得组数最小，这里直接正序求是因为这样的求法得到的是升序数组（其实二分法只适于求上升子序列的原因也就是因为其能得到升序数组）

完整代码：

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1010;
const int INF = 0x3f3f3f3f;

int n;
int q[N];
int f[N], g[N];

int main(){
    while(cin>>q[n])n++;
    
    memset(f, 0x3f, sizeof f);
    memset(g, 0x3f, sizeof g);
    
    int ans = 0;
    for(int i = n-1; ~i; i--){
        * upper_bound(f, f+n, q[i]) = q[i];
    }
    
    while(f[ans] != INF) ans++;
    cout<<ans<<endl;
    
    int cnt = 0;
    for(int i = 0; i < n; i++){
        * lower_bound(g, g+n, q[i]) = q[i];
    }
    
    while(g[cnt] != INF) cnt++;
    cout<<cnt<<endl;
    return 0;
}

（为了便于理解这里用了两个遍历循环，但实际上可以容易地合并为一个循环）

导弹防御系统

题面描述：题目给定一个长度为 n 的数组 w[n] ，要求我们用最少的上升子序列和下降子序列完全覆盖该数组，求该方案的上升子序列和下降子序列的总个数

原题链接：AcWing 187. 导弹防御系统

方法：O(n2n)O_{(n2^n)}

这个题肯定是拦截导弹的进阶版啦，思路就是dfs + 拦截导弹

dfs当前数应该划为上升子序列中还是下降子序列中，应该要注意到这里的n <= 50 太大了但是剪枝就能过（神奇）

完整代码：

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
#include<iostream>
#include<cstdio>
using namespace std;

const int N = 60;

int n;
int q[N];
int up[N], down[N];
int ans;

void dfs(int u, int su, int sd){
    if(su+sd >= ans) return;
    if(u == n){
         ans = su+sd;
         return;
    }
    
    //情况1：将当前数放到上升子序列中
    int k = 0;
    while(k < su && up[k] >= q[u]) k++;
    int t = up[k];
    up[k] = q[u];
    if(k < su) dfs(u+1, su, sd);
    else dfs(u+1, su+1, sd);
    up[k] = t;
    
    //情况2：将当前数放在下降子序列中
    k = 0;
    while(k < sd && down[k] <= q[u]) k++;
    t = down[k];
    down[k] = q[u];
    if(k < sd) dfs(u+1, su, sd);
    else dfs(u+1, su, sd+1);
    down[k] = t;
}

int main(){
    while(cin>>n, n){
        for(int i = 0; i < n; i++) cin>>q[i];
        
         ans = n;
         dfs(0, 0, 0);
         
         cout<<ans<<endl;
    }
    
    return 0;
}

最长公共子序列（LCS）

题面描述：给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

原题链接：Leetcode1143. 最长公共子序列

方法：复杂度 On2O_{n^2}

状态表示：

  1. 数组结构：由两个字符串长度为规模的二维数组（len_a * len_b的二维数组）
  2. 位置信息：第一个字符串的前 ii 个字母构成的子串，与第二个字符串的前 jj 个字母构成的子串（dp[i][j]）
  3. 数值信息：两个子串的最长公共子序列长度

状态计算：

  1. a[i] == b[j] 则 dp[i][j] = max(dp[i-1][j-1]+1, dp[i][j-1], dp[i-1][j])
  2. a[i] != b[j] 则 dp[i][j] = max(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])

值得注意的是，这里的状态计算实际上是包含了四种状态是转移分别是（a[0,i]和b[0,j]匹配）、（a[0,i-1]与b[0,j-1]匹配）、（a[0,i-1]与b[0,j]匹配）、（a[0,i]与b[0,j-1]匹配），但是第二种情况一定是被第三种和第四种情况涵盖的即dp[i-1][j] >= dp[i-1][j-1] && dp[i][j-1] >= dp[i-1][j-1]，故当 a[i] != b[j] 时，我们可以只令 dp[i][j] = max(dp[i][j-1], dp[i-1][j]) 即可。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<cstdio>
using namespace std;

const int N = 1010;
int n, m;
char a[N], b[N];
int dp[N][N];

int main(){
    cin>>n>>m;
    scanf("%s%s", a+1, b+1);
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            if(a[i]==b[j]) dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1);
            // else dp[i][j] = max(dp[i][j], dp[i-1][j-1]);
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}

最长公共上升子序列

题面描述：给定两个长度为 n 个数组 a[n],b[n]，求两个数组的 最长公共上升子序列的长度

原题链接：AcWing 272. 最长公共上升子序列

方法1：O(n3)O_{(n^3)}

状态表示：

  1. 数组结构：两维长度分别为a数组长度和b数组长度的二维数组
  2. 位置信息：维护a[0~i]和b[0~j]且以b[j]j结尾的的最长公共上升子序列
  3. 数值信息：最长公共上升子序列长度

状态计算：

  1. 考虑当已经确认f[i-1][j]即已经确定了以b[j]结尾的a[0~i-1]与b[0~j]中的最长上升子序列长度，此时考虑以b[j]结尾的a[0~i]与b[0~j]的最长上升子序列长度
  2. 如果a[i]与b[j]不相等，也就意味着这时无法扩充最长公共子序列的长度，也即当前的值直接继承f[i-1][j]的值即可
  3. 如果a[i]与b[j]相同，也就意味着这时有机会扩充最长公共子序列，向其前面b[0~j-1]中找到与a[0~i]配对的且值比自己小的最长的公共上升子序列长度作为然后将其加一（加上自己）即可

完整代码：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N  = 3010;

int n;
int a[N], b[N];
int f[N][N];

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            f[i][j] = f[i-1][j];
            if(a[i] != b[j]) continue;
            for(int k = 0; k < j; k++){
                if(b[k] < b[j]) f[i][j] = max(f[i][j], f[i][k]+1);
            }
        }
    }
    
    int ans = 0;
    for(int i = 1; i <= n; i++) ans = max(ans, f[n][i]);
    
    cout<<ans;
    return 0;
}

方法二：O(n2)O_{(n^2)} （优化）

思路：

  1. 代码虽然正确但是时间复杂度超过了限制，所以需要进行优化

  2. 这里可以优化的最可能的就是最内层循环（查找比自己数值小的且与a[0~i]构成最长公共上升子序列的子段链接到其后）因为这里的重复计算非常多

  3. 我们可以发现，进行第三重循环的条件是a[i] == b[j]这里的比b[j]数值小的且与a[0~i]构成最长公共上升子序列的长度可以等效于比a[i]数值小的，从而可以维护一个最大值保存第二重循环遍历到的比a[i]小的且与a[0~i]构成的最长公共上升子序列长度，从而就可以避免在第二层循环小查找这个最大数的又一层循环

  4. 这里的maxv维护的是比a[i]小的b[j]中a[0~i]与b[0~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<cstdio>
#include<algorithm>
using namespace std;

const int N  = 3010;

int n;
int a[N], b[N];
int f[N][N];

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
    
    for(int i = 1; i <= n; i++){
        int maxv = 0;
        for(int j = 1; j <= n; j++){
            f[i][j] = f[i-1][j];
            if(a[i] == b[j]) f[i][j] = max(f[i][j], maxv+1);
            if(a[i] > b[j]) maxv = max(maxv, f[i-1][j]);
        }
    }
    
    int ans = 0;
    for(int i = 1; i <= n; i++) ans = max(ans, f[n][i]);
    
    cout<<ans;
    return 0;
}

趁着这个优化总结一下常见优化策略：

  1. 维护一个数：最大值、最小值
  2. 维护一个序列：单调栈、单调队列
  3. 维护一个表：记忆化搜索

背包问题

装箱问题

题面描述：有一个箱子容量为V（正整数，0⩽V⩽200000 \leqslant V \leqslant 20000），同时有n个物品（0<n⩽300 < n \leqslant 30，每个物品有一个体积（正整数）；要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

原题链接：洛谷 P1049 NOIP2001 普及组 装箱问题

备用链接：AcWing 1024. 装箱问题

方法：On2O_{n^2}

将物品的质量同时作为物品的价值就可以将问题转换为 01背包问题 啦

于是就有了转移方程 fi=max(fi, fi−w[i]+w[i])f_i = max(f_i, \ f_{i-w[i]}+w[i])​​​ 问题解决

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstdio>
using namespace std;

const int V = 20010, N = 40;

int f[V];
int v, n, arr[N];

int main() {
	cin >> v >> n;

	for (int i = 1; i <= n; i++)
		cin >> arr[i];


	for (int i = 1; i <= n; i++) {
		for (int j = v; j >= arr[i]; j--) {
			f[j] = max(f[j], f[j - arr[i]] + arr[i]);
		}
	}

	cout << v - f[v];
}

开心的金明

题面描述：m件物品价格和重要度分别为v[j] w[j]，现在有n元钱要求在花费不超过n的前提下使得购买的商品的价格与重要度乘积最大

原题链接：洛谷 P1060 NOIP2006 普及组 开心的金明

备用链接：AcWing 426. 开心的金明

方法：On2O_{n^2}

就01背包原题了，权重就是v[i] * w[i]，这里原题题干上的 w[i] 实际上是没必要存在的，所有直接将价值存为 v[i] * w[i] 套01背包模板即可，列出转移方程 fi=max(fi, fi−v[i]+w[i]×v[i])f_i = max(f_i, \ f_{i-v[i]}+w[i]\times v[i])​ 问题解决

完整代码：

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
#include <iostream>
#include <cstdio>
using namespace std;

const int V = 30010, N = 35;

int f[V];
int n, m;
int v[N], w[N];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a;
		cin >> v[i] >> a;
		w[i] = v[i] * a;
	}

	for (int i = 1; i <= m; i++) {
		for (int j = n; j >= v[i]; j--) {
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		}
	}

	cout << f[n];
	return 0;
}

疯狂的采药

题面描述：有m种无限株草药，采药花费时间a[i]得到价值b[i]，问：在时间限定t内采到的最大草药价值为多少

原题链接：洛谷 P1616 疯狂的采药 （完全背包模板）

备用链接：AcWing 423. 采药 （01背包模板）

方法：O(n2)O_{(n^2)}

完全背包模板pass

完整代码：

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
#include <iostream>
#include <cstdio>
using namespace std;

typedef long long LL;

const int T = 1e7 + 10, M = 1e4 + 10;

LL f[T];
int m, t;
int a[M], b[M];

int main() {
	cin >> t >> m;
	for (int i = 1; i <= m; i++)
		cin >> a[i] >> b[i];

	for (int i = 1; i <= m; i++) {
		for (int j = a[i]; j <= t; j++) {
			f[j] = max(f[j], f[j - a[i]] + b[i]);
		}
	}

	cout << f[t];
	return 0;
}

投资的最大效益

题面描述：本金s在n年中投资d种债卷，其中第i中债卷的投资额为a[i]一年后收益为b[i]，问n年后资产总值最大为多少

原题链接：洛谷 P1853 投资的最大效益

方法：OnsdO_{nsd}

注意到投资额的一定是1000的倍数可以避免无效讨论，然后就是多次求完全背包问题了

完整代码：

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int S = 5e4 + 10, N = 50, D = 15;

int f[S];
int s, n, d;
int a[D], b[D];

int main() {
	cin >> s >> n >> d;

	for (int i = 1; i <= d; i++) {
		int x;
		cin >> x >> b[i];
		a[i] = x / 1000;
	}
	for (int k = 0; k < n; k++) {
		memset(f, 0, sizeof f);

		for (int i = 1; i <= d; i++) {
			for (int j = a[i]; j <= s / 1000; j++) {
				f[j] = max(f[j], f[j - a[i]] + b[i]);
			}
		}

		s += f[s / 1000];
	}

	cout << s;
	return 0;
}

砝码称重

题面描述：设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重⩽1000其总重\leqslant 1000），求这些法码能称的不同重量种数

原题链接：洛谷 P2347 NOIP1996 提高组 砝码称重

方法：On2O_{n^2}

可以理解为线性DP问题（有点像斐波那契数列），由于数据太小了可以直接求就行

原本应该可以用布尔数组表示能称的重量的，但是谁让万物皆可哈希呢😂

完整代码：

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
#include <iostream>
#include <cstdio>
#include <vector>
#include <unordered_set>
using namespace std;

int main() {
	int a[6] = {1, 2, 3, 5, 10, 20};
	int n[6];
	for (int i = 0; i < 6; i++)
		cin >> n[i];
	unordered_set<int> s = {0};

	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < n[i]; j++) {
			vector<int> tmp;
			for (auto t : s) {
				if (!s.count(t + a[i]))
					tmp.push_back(t + a[i]);
			}
			for (auto t : tmp) {
				s.insert(t);
			}
		}
	}

	cout << "Total=" << s.size() - 1;
	return 0;
}

二维费用的背包问题

题面描述： NN​ 个物品其中第 ii​ 个物品体积为 viv_i​ 重量为 mim_i​ 价值为 wiw_i​ 现在有一个容量为 VV​ 最大承重 MM​ 的背包，输出最大装下物品的价值。

原题链接：AcWing 8. 二维费用的背包问题

方法： O(NVM)O_{(NVM)}

本题为二维费用背包模板题，简单而言就是在一维背包问题的基础上增加了一维费用，其本质上与一维背包问题相通；

状态转移方程： f[i,j,k]=max(f[i,j,k], f[i−1,j−v1,k−v2]+w)f[i,j,k] = max(f[i, j, k],\ f[i-1, j-v_1, k-v_2] + w)

而后分析可知问题是二维费用的01背包问题，根据01背包的状态压缩方法可以对状态方程压缩掉其中一维。

完整代码：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 110, M = 110;

int k, n, m;
int f[N][M];
int v1, v2, w;

int main(){
    cin>>k>>n>>m;
    for(int i = 0; i < k; i++){
        cin>>v1>>v2>>w;
        for(int j = n; j >= v1; j--){
            for(int r = m; r >= v2; r--){
                f[j][r] = max(f[j][r], f[j-v1][r-v2]+w);
            }
        }
    }
    
    cout<<f[n][m];
    return 0;
}

宠物小精灵之收服

题面描述：小智有精灵球 nn 个并且皮卡丘体力为 mm 去收服 kk 只野生精灵，其中收服第 ii 只精灵的精灵球消耗为 aia_i 皮卡丘体力消耗为 bib_i ，问如何捕获精灵使得皮卡丘体力不为0的前提下捕获尽可能多的精灵并且皮卡丘体力消耗最小，输出最多捕获精灵个数和皮卡丘最大剩余体力。

原题链接：AcWing 1022. 宠物小精灵之收服

方法：O(nmk)O_{(nmk)}

二维费用的01背包问题，f[i,j,k]f[i, j, k] 表示：仅考虑前 ii 个精灵在消耗精灵球数量不超过 jj 个皮卡丘体力消耗不超过 kk 的前提下能捕获的最多精灵数

转移方程为 f[i,j,k]=max(f[i,j,k], f[i−1,j−ai,k−bi]+1)f[i,j,k] = max(f[i, j, k],\ f[i-1, j-a_i, k-b_i]+1) ，根据前面的01背包问题的处理方式显然可以压缩掉表示前 ii 个精灵的那一维

输出f[n][m]即为最多可捕获的精灵个数，然后找到做小的 kk 使得 f[n][k]==f[n][m−1]f[n][k] == f[n][m-1] 即可。

需要格外注意的就是皮卡丘的体力不能为 0 也就是皮卡丘的体力消耗不能大于 mm

完整代码：

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<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1010, M = 510;

int n, m, k, v1, v2;
int f[N][M];

int main(){
    cin>>n>>m>>k;
    
    for(int i = 1; i <= k; i++){
        int v1, v2;
        cin>>v1>>v2;
        for(int j = n; j >= v1; j--){
            for(int k = m-1; k >= v2; k--){
                f[j][k] = max(f[j][k], f[j-v1][k-v2]+1);
            }
        }
    }
    
    cout<<f[n][m-1]<<" ";
    
    int k = m-1;
    while(k > 0 && f[n][k-1] == f[n][m-1]) k--;
    cout<<m-k<<endl;
    return 0;
}

潜水员（“至少为”表述）

题面描述：有 KK 个物品两维费用的物品，对于第 ii 种物品第一维费用为 v1iv_{1i} 第二维费用为 v2iv_{2i} 价值为价值为 wiw_i ，问在第一维费用不小于 nn 第二维费用不小于 mm 的前提下的最小总价值为多少？输出最小总价值。

原题链接：AcWing 1020. 潜水员

方法：O(knm)O_{(knm)}

本题的本质还是二维费用背包问题，但是本题的状态表示会与前面的又细微差别，注意本题的描述中：“费用不小于XX时”，而往前的描述为：“费用不超过XX时”这里引出了讨论的重点——背包问题中状态定义的三种描述：

  1. 不超过系列（费用不超过XX时）

    不超过系列问题都是配合着价值最大化而存在的（考虑费用不超过XX时的最小价值不就是啥也不取吗）

    初始化：所有状态都可以初始化为0，因为（以一维费用状态压缩为例）对于状态dp[i]而言状态dp[0]一定能表示费用不超过i的一个状态，所以所有状态都可以从dp[0]转移过来，也就是所有状态值在没有拿取任何物品时也会被dp[0]首先初始化

    负值费用：对于不超过问题，负数费用既没有存在意义也没有实际意义

  2. 恰好等于系列（费用恰好为XX时）

    恰好等系列需要同时考虑最大化价值与最小化价值两种情况

    初始化：除了原始状态（费用全为0时）的其他费用都无法被初始化成功，因为还没有任何理由确认存在对于状态dp[i]而言存在费用恰好为i的组合。转而言之，当前装填不可达也就是可以对于最小价值问题初始化为INF，最大价值问题初始化为-INF，而仅存的可以确认可达的初始转态值只有初始费用为0的状态；

    负值费用：对于恰好等于问题，负数费用既没有存在意义也没有实际意义

  3. 至少为系列（费用至少为XX）

    费用至少为系列需要配合考虑价值最小化问题（考虑费用至少为的化可以直接将全部的）

    初始化：所有状态理论上都可以初始化为所有价值总和，但为了与状态表示相符（初始状态表示不取任何物品）所有状态的最小值都无法判断也即应该置为INF表示当前状态不可达，而仅dp[0]状态是可达的需要置为0

    负值费用：对于至少为问题负数费用是有存在意义的（但是没有实际意义），当负数费用出现时没有实际意义的状态本不应该出现，但是对于至少为负值而言可以转换为至为0而存在计算意义

而本题就是一个“至少为”系列的二维费用的01背包问题

完整代码：

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
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int N = 25, M = 85;

int n, m, k;
int f[N][M];

int main(){
    cin>>n>>m>>k;
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    
    while(k--){
        int v1, v2, w;
        cin>>v1>>v2>>w;
        for(int i = n; i >= 0; i--){
            for(int j = m; j >= 0; j--){
                f[i][j] = min(f[i][j], f[max(0, i-v1)][max(0, j-v2)]+w);
            }
        }
    }
    
    cout<<f[n][m];
    return 0;
}

数字组合（求方案数）

题面描述：给定 NN 个正整数 A1,A2,…,ANA_1,A_2,…,A_N 从中选出若干个数，使它们的和为 MM，求有多少种选择方案。

原题链接：AcWing 278. 数字组合

方法： ONMO_{NM}

状态表示：

  1. 数组结构：一维长度为正整数个数 NN，另一维长度为要求的和 MM 加一的二维数组（当然可以状态压缩）
  2. 位置信息：表示当前考虑前 ii 个数其和组成大小为 jj 的数
  3. 数值信息：方案数

状态计算：

  1. 01背包的转移方程

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<cstdio>
using namespace std;

const int N = 10010;
int n, m;
int f[N];

int main(){
    cin>>n>>m;
    f[0] = 1;
    for(int i = 0; i < n; i++){
        int v;
        cin>>v;
        for(int j = m; j >= v; j--){
            f[j] += f[j-v];
        }
    }
    
    cout<<f[m]<<endl;
    return 0;
}

买书（求方案数）

题面描述：有四种无线个数的物品，体积分别为10、20、50、100，求将这些物品恰好放入体积为 nn 的背包的方案数

原题链接：AcWing 1023. 买书

方法：O(n)O_{(n)}

  1. 本题是“恰好是”表述系列的完全背包求方案数问题，将前面的几种问题糅合在一起 但是其实很简单

完整代码：

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
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int N = 110;
int n;
int f[N];

int main(){
    cin>>n;
    if(n%10){cout<<0; return 0;}
    n/=10;
    memset(f, 0, sizeof f);
    f[0] = 1;
    int d[4] = {1, 2, 5, 10};
    
    for(int i = 0; i < 4; i++){
        for(int j = d[i]; j <= n; j++){
            f[j] += f[j-d[i]];
        }
    }
    
    cout<<f[n];
    return 0;
}

多重背包问题 III

题面描述：有 NN 种物品和一个容量是 VV 的背包。第 ii 种物品最多有 sis_i 件，每件体积是 viv_i ，价值是 wiw_i 。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

原题链接：AcWing 6. 多重背包问题 III

方法：O(NV)O_{(NV)}

  1. 考虑最原始的多重背包的求解方案：

    多重背包问题（图一）

    可以看到 f[i,j]f[i,j]​ 与 f[i,j+v]f[i, j+v]​ 它们在计算推导的过程中重复计算了大量相同的项，而 f[i,j+1]f[i, j+1]​ 与 f[i,j+1+v]f[i, j+1+v]​ 也在推导的过程中计算了大量相同的项，据此我们可以根据这个特性减少计算量。

  2. 我们可以发现所有背包容量（j）对于当前物品体积（v）同余的项都在计算的过程中重复计算了大量相同的项其中相同的项之间也是同余于当前物品体积的，而背包容量与当前物品体积不同余的项之间在计算时没有相同项重复计算的情况；

    据此，我们可以将背包容量更具对当前物品体积v取模得到的余数分为v类，在每一类的计算过程中根据重复计算设计方案来减少/避免重复计算；

  3. 现在考虑第r类（所有当前背包容量j与当前物品体积v取模的余数都为r的项，即所有与r同余于当前物品体积v的j）

    多重背包问题（图二）

  4. 上图中已经说明了是用到了滑动窗口来解决问题的，下面我们来分析一下如何维护这个滑动窗口：

    首先我们很容易分析得到这个滑动窗口的大小就是当前物品的数量；

    其次我们在滑动窗口中维护的值为当前滑动窗口内的最大值，这就很容易联想到“滑动窗口内的最大值”模板题了，而这题的解法就是用到了单调队列维护滑动窗口的（不了解滑动窗口的读者可以自行阅读单调栈和单调队列）；

  5. 但是我们可以发现窗口内的数的表达式是在不断变换的，而对于“滑动窗口内的最大值”而言维护的窗口内的数值是固定不变的

    对于本题的需求而言我们显然不能单纯地将具体的值存入单调队列中；

    首先，我们考虑在滑动窗口内的数的表达式的相同点选取具有代表性的第一项 f[i−1,r]+xwf\left[i-1,r\right] + xw 在不断滑动窗口的过程中不变的是 f[i−1,r]f\left[i-1,r\right] 项，变化的只有 +xw+xw 项，而这里的 x 的值实际上就是将x 个物品装入已经装入体积为 j′j^{'} 的背包中使给背包装入的物品的总体积为当前背包容积 j，所有这里的 x 的计算公式就是 x=(j−j′)/vx = (j-j^{'})/v ；

    就此我们可以发现在滑动窗口中任意两项之间的的差距一定是f[i−1,j1]−f[i−1,j2]−(j1−j2)/v×wf[i-1, j_1]-f[i-1, j_2]-(j_1-j_2)/v\times w ，这也就意味着我们在单调队列中只需要保存 j1,j2,...,jnj_1, j_2, ..., j_n 的值即可，在维护单调队列时只需要比较 f[i−1,ji]−ji/v×wf[i-1, j_i] - j_i/v\times w​​ 的值即可。

    （理解到这里还是很重要的但好像y总和很多博文都讲得比较含糊）

  6. 思路讲解结束了，我们现在总结一下前面的分析结论：

    1. 对于每个体积为 vv 的物品，将背包容积 mm 按照同余于 vv 分为 vv 类，分别求值
    2. 当前 f[i,j]f[i, j] 的值的求法就是取大小为当前物品数量 ss 的滑动窗口内的最大值
    3. 滑动窗口由单调队列来维护，其值维护了当前背包容量 jij_i ，具体判断项的入队与弹出由 f[i−1,ji]−ji/v×wf[i-1, j_i] - j_i/v\times w 来决定

完整代码：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 20010;
int n, m;
int f[N][N];
int q[N];


int main(){
    cin>>n>>m;
    
    for(int i = 1; i <= n; i++){
        int v, w, s;
        cin>>v>>w>>s;
        
        //分成r类
        for(int r = 0; r < v; r++){
            int hh = 0, tt = -1;
            for(int j = r; j <= m; j+=v){
                
                f[i][j] = f[i-1][j];
                
                //超过滑动窗口的体积
                if(hh <= tt && (j-q[hh])/v > s) hh++;
                if(hh <= tt) f[i][j] = max(f[i][j], f[i-1][q[hh]]+(j-q[hh])/v*w);
                
                //弹出旧且表达式值小于当前值的项
                while(hh <= tt && f[i-1][q[tt]]-q[tt]/v*w <= f[i-1][j]-j/v*w) tt--;
                
                q[++tt] = j;
            }
        }
    }
    
    cout<<f[n][m]<<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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 20010;

int n, m;
int f[N], g[N], q[N];

int main(){
    cin>>n>>m;
    for(int i = 0; i < n; i++){
        int v, w, s;
        cin>>v>>w>>s;
        memcpy(g, f, sizeof f);
        for(int j = 0; j < v; j++){
            int hh = 0,  tt = -1;
            for(int k = j; k <= m; k+=v){
                if(hh <= tt && q[hh] < k-s*v) hh++;
                if(hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh])/v * w);
                while(hh <= tt && g[q[tt]]-(q[tt]-j)/v * w <= g[k]-(k-j)/v * w) tt--;
                q[++tt] = k;
            }
        }
    }
    
    cout<<f[m]<<endl;
    return 0;
}

庆功会

题面描述：共有 nn 种物品，第 ii 种的体积为 viv_i 数量为 sis_i 价值为 wiw_i ，背包最大容量为 mm 求能得到的最大价值

原题链接：AcWing 1019. 庆功会

方法：O(nm)O_{(nm)}

  1. 本题是多重背包的应用，数据量在朴素法 O(nmsmax)O_{(nms_{max})} 也能通过，但是这里用了优先队列优化法

完整代码（朴素）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<cstdio>
using namespace std;

const int N = 6010;
int n, m;
int f[N];

int main(){
    cin>>n>>m;
    for(int i = 0; i < n; i++){
        int v, w, s;
        cin>>v>>w>>s;
        for(int j = m; ~j; j--){
            for(int k = 0; k <= s && k*v <= j; k++){
                f[j] = max(f[j], f[j-k*v]+k*w);
            }
        }
    }
    
    cout<<f[m]<<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
37
38
39
40
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 20010;
int n, m;
int f[N][N];
int q[N];


int main(){
    cin>>n>>m;
    
    for(int i = 1; i <= n; i++){
        int v, w, s;
        cin>>v>>w>>s;
        
        //分成r类
        for(int r = 0; r < v; r++){
            int hh = 0, tt = -1;
            for(int j = r; j <= m; j+=v){
                
                f[i][j] = f[i-1][j];
                
                //超过滑动窗口的体积
                if(hh <= tt && (j-q[hh])/v > s) hh++;
                if(hh <= tt) f[i][j] = max(f[i][j], f[i-1][q[hh]]+(j-q[hh])/v*w);
                
                //弹出旧且表达式值小于当前值的项
                while(hh <= tt && f[i-1][q[tt]]-q[tt]/v*w <= f[i-1][j]-j/v*w) tt--;
                
                q[++tt] = j;
            }
        }
    }
    
    cout<<f[n][m]<<endl;
    return 0;
}

区间DP

区间DP问题一般涉及到区间的合并而状态表示一般是用于维护区间的状态，即dp[i][j] 一般用于维护原数组下标区间[i,j]的元素的某种属性。

区间DP的特点：

合并：即将两个或多个部分整合起来，当然也可以反过来

特征：问题能够分解为两两合并的形式

求解：对整个问题设最优值，枚举合并点，将原问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优解

石子合并

题面描述： 有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。

原题链接：AcWing 282. 石子合并

方法：复杂度 On3O_{n^3}

状态表示：

  1. 数组结构：两维长度都是原数组长度的二维数组表示
  2. 位置信息：维护原数组的区间 [i, j] 内的所有元素集合
  3. 数值信息：将区间 [i, j] 内所有元素合并为一堆的最小体力花费

状态计算：

  1. 枚举待合并的区间长度（从小到大枚举）
  2. 枚举待合并的区间的起始位点，这样就可以维护起一个[l,r]的区间
  3. 枚举分断点使得整个区间分为两个子区间，这样将两个子区间合并所花费的体力值就等于将两个子区间内的元素合并后再将两个“合并后的区间”合并的值了f[l][k]+f[k+1][r]+s[r]-s[l-1]

这里的计算没有像线性DP一样有一个很清晰的（线性的）转移顺序，而是使用了类似分治的思维将大区间分为小的区间再由已计算出的小区间的值去得到大区间的值

完整代码：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 310;

int n;
int s[N];
int f[N][N];

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>s[i];
    for(int i = 1; i <= n; i++) s[i] += s[i-1];
    
    for(int len = 2; len<=n; len++){
        for(int i = 1; i + len-1 <= n; i++){
            int l = i, r = i+len-1;
            f[l][r] = 1e8;
            for(int k = l; k < r; k++){
                f[l][r] = min(f[l][r], f[l][k]+f[k+1][r]+s[r]-s[l-1]);
            }
        }
    }
    
    cout<<f[1][n];
    return 0;
}

数位DP

简介：这一个数字按个、十、百、千…等位一位一位划分，就可以得到一串数，这样的每一个数就成为数位。而数位DP一般是用于解决这样针对数位的特定问题的，一般需要用到数位DP 的无非就是这样的针对数位考虑并且暴力地枚举每一个数并进行拆分是会超时的题。

解决这样的问题用到了前缀和的思想：假设我们已经实现了函数count(int n, int x)可以计算从1到n的数的数位中x的个数，那么计算从a到b的数的数位中x的个数就可以表示为count(b,x) - count(a-1,x)·

count(int n,int x)函数的实现：我们现在假设n为一个七位数abcdefg，现在要求出n的第4位为x的数的个数，构造一个这样的数ABCxEFG代表第4位为x的在0到abcdefg范围内的数

  1. 当ABC取0 ~ abc-1时，EFG取遍0 ~ 999都恒有ABCxEFG < abcdfeg即存在abc*1000个这样的数

  2. 当ABC取abc时

    （1）若b < x则恒有ABCxEFG > abcdefg即不存在这样的数

    （2）若b = x则有当EFG取0 ~ efg时有ABCxEFG <= abcdefg即存在efg+1个这样的数

    （3）若b > x则有EFG取遍0 ~ 999都恒有ABCxEFG < abcdfeg即存在1000个这样的数

  3. 边界情况，当x = 0时，由于ABC不能从000开始取而是从001开始需要特判

计数问题

题面描述：试计算在区间 1 到 n 的所有整数中，数字 x（ 0⩽x⩽90 \leqslant x \leqslant 9​ ）共出现了多少次？例如，在 1 到 11 中，即在 1,2,3,4,5,6,7,8,9,10,11 中，数字 1 出现了 4 次。

原题链接：AcWing 338. 计数问题

解题思路如上（好像并不能写出状态转移🤣)

完整代码：

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
#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;

//返回从l到r的这段数
int get(vector<int> &num, int l, int r){
    int ans = 0;
    for(int i = l; i >= r; i--){
        ans  = ans*10 + num[i];
    }
    return ans;
}

//10的x次方
int power10(int x){
    int ans = 1;
    while(x--){
        ans *= 10;
    }
    return ans;
}

long long count(int n, int x){
    if(!n) return 0;
    
    vector<int> num;
    while(n){
        num.push_back(n%10);
        n/=10;
    }
    
    n = num.size();
    
    long long ans = 0;
    // 减!x是确保x不被考虑为前导0
    for(int i = n-1-!x; i>=0; i--){
        if(i < n-1){
            ans += get(num, n-1, i+1)*power10(i);
            if(!x) ans -= power10(i);
        }
        
        if(num[i] == x) ans += get(num, i-1, 0)+1;
        else if(num[i] > x) ans += power10(i);
    }
    
    return ans;
}

int main(){
    int a, b;
    while(cin>>a>>b, a || b){//这里用到了逗号表达式，返回的值为最后一个表达式的返回值
        if(a>b) swap(a, b);
        
        for(int i = 0; i < 10; i++){
            cout<<count(b, i)-count(a-1, i)<<" ";
        }
        puts("");
    }
}

状压DP

简介：状态压缩DP就是将整数的表示压缩成位的表示来实行啊优化转移的目的（与bitmap及其他状态压缩有是相似的是同一种压缩手段的不同应用而已）

蒙德里安的梦想

题面描述：

image-20220105104543527

原题链接：AcWing 291. 蒙德里安的梦想

方法：复杂度 Om22nO_{m2^{2n}}

状态表示：

  1. 数组结构：第一维为列数（m+1m+1），第二维为2的行数次方（2n2^{n}）的二维数组
  2. 位置信息：第一维表示当前列，第二维是状态压缩后的当前列放置长方形的状态；其中用0表示当前方格使用竖向的长方形，1表示横向的长方形，由于不考虑当前列的排放是否正确即竖向的长方形是否都能占据两个空间则总共能出现的状态就有00...0 ~ 11...1共2n2^n种
  3. 数值信息：表示当前列i是j种状态时共存在dp[i][j]种可能

状态计算：

  1. 上述的位置信息中已经表述了可能会存在某些状态不能排列满连续的竖向长方形，这里先用一个布尔数组区分这些不可能的状态。
  2. 在布尔数组中确定了可能存在的状态中每一列的竖向排列的长方形的位置，即接下来只需要考虑所有放置的横向长方形与前一列放置的横向长方形是否产生冲突，以及当前列的放置情况与前一列多出来的一个横向小方格构成的状态是否满足能放置满竖向长方形的要求。
  3. 当前行当前状态的值就等于前一行中的所有满足不冲突且与前一行的状态构成的新状态满足竖向放置要求的所有状态的所有可能情况的总和。
  4. 最终的结果就是最后一行不放置新的横向长方形（状态为00...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<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 12, M = 1 << N;

int n, m;
long long dp[N][M];
bool st[M];

int main(){
    int n, m;
    while(cin>>n>>m, n || m){
        memset(dp, 0, sizeof dp);
        
        for(int i = 0; i < 1 << n; i++){
            st[i] = true;
            int cnt = 0;
            for(int j = 0; j < n; j++){
                if(i>>j & 1){
                    if(cnt&1) break;
                    cnt = 0;
                }
                else cnt++;
            }
            if(cnt&1) st[i] = false;
        }
        
        dp[0][0] = 1;
        for(int i = 1; i <= m; i++){
            for(int j = 0; j < 1<<n; j++){
                for(int k = 0; k < 1<<n; k++){
                    if((j&k)==0 && st[j|k]) dp[i][j] += dp[i-1][k];
                }
            }
        }
        
        cout<<dp[m][0]<<endl;
    }
}

最短曼哈顿路径

题面描述：给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。（Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次 一笔画问题）

原题链接：AcWing 91. 最短Hamilton路径

方法：复杂度 On2 2nO_{n^2\ 2^n}

状态表示：

  1. 数组结构：第一维为2的节点个数次方（2n2^n），第二维为节点个数（n+1n+1）

  2. 位置信息：第一维代表已经走过的所有节点（状态压缩），第二维代表着现在所在的节点编号

  3. 数值信息：代表着按规则走过第一维标识的所有节点并且最终到达第二维表示的节点的最短路径

状态计算：

  1. 当前状态的值等于从已经走过的节点出发走到当前节点的值之和的最小值即状态转移方程： f[i][j]=min(f[i][j],f[i−(1<<k)][k]+w[k][j])f[i][j] = min(f[i][j], f[i-(1<<k)][k]+w[k][j])
  2. 初始将所有状态的值置为INF并将初始点置为0
  3. 枚举所有可能的 2n2^n 种已经经过的节点状态
  4. 枚举法从每种节点状态中选择出来一个节点充当终止节点
  5. 枚举每一个状态可能的前一个状态从而通过状态转移得到当前状态的最短路径
  6. 最终的结果就是走完当前的所有节点并且最终到达的节点是最后一个节点的状态

Tips：由于第一次枚举是枚举了走过的所有节点的状态而且是使用了从小到大枚举，故可以得到已经枚举到的状态中一定已经计算了当前枚举到的所有可能的前一个状态，故状态转移是合理的

完整代码：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 20, M = 1 << N;

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

int main(){
    cin>>n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin>>w[i][j];
        }
    }
    
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    
    for(int i = 0; i < 1<<n; i++){
        for(int j = 0; j < n; j++){
            if(!(i>>j & 1)) continue;
            for(int k = 0; k < n; k++){
                if(j != k && (i>>k & 1)){
                    f[i][j] = min(f[i][j], f[i-(1<<j)][k] + w[k][j]);
                }
            }
        }
    }
    
    cout<<f[(1<<n)-1][n-1]<<endl;
    return 0;
}

树形DP

简介：树形 DP，即在树上进行的 DP。由于树固有的递归性质，树形 DP 一般都是递归进行的。

没有上司的舞会

题面描述：某大学有 nn 个职员，编号为 1...n1 ... n。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 rir_i，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

原题链接：洛谷 P1352 没有上司的舞会

方法：复杂度 OnO_{n}

状态表示：

  1. 数组结构：两个数组长度为节点个数的一位数组（用二维数组表示）
  2. 位置信息：数组位置表示仅关注以当前节点为根节点的子树参与宴会，其中一个数组表示当前节点（子树的根节点）参加舞会（第二维设为1），另一个表示当前节点不参加舞会（第二维设为0）
  3. 数值信息：表示当前子树能够获得的最大快乐指数

状态计算：

  1. 若选择当前节点（根节点），则对于其下子树而言子树的根节点必定不能参加舞会，故转移方程为 f[i][1]=happy[i] + ∑f[x][0]f[i][1] = happy[i]\ +\ \sum{f[x][0]} （其中 x 代表 i 的子节点）
  2. 若不选择当前节点，则对于其下子树而言子树的根节点可参加舞会也可不参加舞会但要求结果最大，故转移方程为 f[i][0]=∑max⁡(f[x][1],f[x][0])f[i][0] = \sum{\max{(f[x][1], f[x][0])}}
  3. 显然这样的状态转移方程是通过递归实现的

完整代码：

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 6010;

int n;
int happy[N];
int h[N], e[N], ne[N], idx;
int f[N][2];
bool has_father[N];

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u){
    f[u][1] = happy[u];
    
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        dfs(j);
        f[u][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];
    }
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &happy[i]);
    
    memset(h, -1, sizeof h);
    
    for(int i = 0; i < n-1; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        has_father[a] = true;
        add(b, a);
    }
    
    int root = 1;
    while(has_father[root]) root++;
    dfs(root);
    
    cout<<max(f[root][0], f[root][1]);
    return 0;
}

记忆化搜索

简介：记忆化搜索给人的感觉不像是DP而更像是搜索，记忆化则更多的是对搜素的过程提供一种优化，然而这样的搜素由于具备最优子结构和重叠子问题的特点而可以使用一个辅助的记忆化数组来记录每次得到的最优子解减少（甚至避免）计算重叠的子问题而得到很好的优化。

记忆化搜索的一般思路：

  1. 写出暴搜程序（最好的DFS）
  2. 判断那一部分是最优子解
  3. 添加记忆化数值以避免计算重叠的子问题

滑雪

题面描述：Michael 喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：

1
2
3
4
5
1   2   3   4   5
16  17  18  19  6
15  24  25  20  7
14  23  22  21  8
13  12  11  10  9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度会减小。在上面的例子中，一条可行的滑坡为 24－17－16－1（从 24 开始，在 1 结束）。当然 25－24－23－…－3－2－1 更长。事实上，这是最长的一条。

原题链接：洛谷 P1434 SHOI2002滑雪

方法：复杂度 OnmO_{nm}

状态表示：

  1. 数组结构：与原矩阵大小相同的二维矩阵
  2. 位置信息：表示从该点与原矩阵对应的点出发
  3. 数值信息：从该点出发所能划的最长距离

状态计算：

  1. 初始化记忆数组为 -1 （即不可能存在的状态），用以表示未计算的空值
  2. 遍历矩阵上的每个点作为起点然后使用DFS（深搜）找到可能路径，并将所有已经得到的确定解记录在记忆化数组中，以备下次使用
  3. 最终的结果就是记忆化数组中记录的最大值

注意：本题能使用深搜就意味着搜索的过程是拓扑图（即子问题的计算过程中不存在依赖回路）

完整代码：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 310;

int n, m;
int h[N][N];
int f[N][N];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

int dp(int x, int y){
    int &v = f[x][y];
    
    if(v != -1) return v;
    
    v = 1;
    for(int i = 0; i < 4; i++){
        int a = x+dx[i], b = y+dy[i];
        if(1 <= a && a <= n && 1 <= b && b <= m && h[a][b] < h[x][y]){
            v = max(v, dp(a, b)+1);
        }
    }
    
    return v;
}

int main(){
    cin>>n>>m;
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            scanf("%d", &h[i][j]);
        }
    }
    
    memset(f, -1, sizeof f);
    
    int ans = 0;
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            ans = max(ans, dp(i, j));
        }
    }
    
    cout<<ans;
    return 0;
}