目录

写给自己的笔记,学一个写一个

我坚信把这些模型学会就可以横扫了

持续更新中,也欢迎大佬指出错误,

1.数学三角模型:

1.摘花生

2.最低通行费

3.方格取数:

4.传纸条

最长上升子序列模型

1.怪盗基德的滑翔翼

2.登山

3.合唱队形

3.友好城市

4.最长上升子序列的和

5.导弹拦截

6. 导弹防御系统

7. 最长公共上升子序列

背包模型:

1.采药

2.装箱问题

3.宠物小精灵之收服

3.数字组合

完全背包:

4.买书

6.货币系统(完全背包求解最大无关向量组个数)

7.多重背包问题三

8.庆功会(多重背包)

9.混合背包:

 10.二维费用的背包问题

11.潜水员:

12.机器分配

13.开心的金明

14.有依赖的背包问题

15.背包问题求方案数

16.背包问题求具体方案

状态机模型

 1大盗阿福

2.股票买卖 IV

3.股票买卖 V

4.密码设计(还没懂,后期补上)

5.修复DNA

状态压缩dp

1.小国王

2.玉米田

3.炮兵阵地

4.愤怒的小鸟

5.宝藏

区间dp

1.环形石子

3.能量项链

4.加分二叉树

树型dp

1.最长路径

         2.树的重心

         3.数字转换

4.二叉苹果树

5.战略游戏【树形DP 状态机模型】

6皇宫看守

---

写给自己的笔记,学一个写一个

我坚信把这些模型学会就可以横扫了

持续更新中,也欢迎大佬指出错误,

1.数学三角模型:

1.摘花生

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

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

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

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

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

思路:这其实是一个简单的数字三角模型的题

1.  
   #include<iostream>
2.  
   #include<cstring>
3.  
   using namespace std;
4.  
   const int maxn =1010;
5.  
   int f[maxn][maxn];
6.  
    
7.  
   int w[maxn][maxn];
8.  
   int main(){
9.  
   int t;
10.  
    cin>>t;
11.  
    while(t--){
12.  
    memset(f,0,sizeof f);
13.  
    int R,C;
14.  
    cin>>R>>C;
15.  
    for(int i=1;i<=R;i ){
16.  
    for(int j = 1;j<=C;j ){
17.  
    cin>>w[i][j];
18.  
    }
19.  
    }
20.  
     
21.  
    for(int i=1;i<=R;i ){
22.  
    for(int j=1;j<=C;j ){
23.  
    f[i][j] = max(f[i-1][j],f[i][j-1]) w[i][j];
24.  
    }
25.  
    }
26.  
     
27.  
    cout<<f[R][C]<<endl;
28.  
    }
29.  
     
30.  
     
31.  
    return 0;
32.  
    }

2.最低通行费

一个商人穿过一个 N×N的正方形的网格，去参加一个非常重要的商务活动。

他要从网格的左上角进，右下角出。

每穿越中间 1 个小方格，都要花费 1 个单位时间。

商人必须在 (2N−1)个单位时间穿越出去。

而在经过中间的每个小方格时，都需要缴纳一定的费用。

这个商人期望在规定时间内用最少费用穿越出去。

请问至少需要多少费用？

注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。

思路:

此题和上一题其实是一样的，当我们在走网格的时候若想从起点到终点，最短距离就是2*N-重复的交点即是2n-1，(即不能往回走)所以我们若将步数控制在2n-1上，那我们的走网格的路径其实就确定了
即每一步只能选择走右或者下

图我就不画了,偷一个:AcWing 1018. 最低通行费 - AcWing

1.  
   #include<iostream>
2.  
   #include<cstring>
3.  
   using namespace std;
4.  
   const int maxn = 110;
5.  
   int f[maxn][maxn];
6.  
   int w[maxn][maxn];
7.  
   int main(){
8.  
   int n;
9.  
   cin>>n;
10.  
    for(int i=1;i<=n;i ){
11.  
    for(int j=1;j<=n;j ){
12.  
    cin>>w[i][j];
13.  
    }
14.  
    }
15.  
    memset(f,0x3f,sizeof f);
16.  
    for(int i=1;i<=n;i ){
17.  
    for(int j=1;j<=n;j ){
18.  
    if(i==1&&j==1)f[i][j] =w[i][j];
19.  
    else{
20.  
    f[i][j] = min(f[i-1][j],f[i][j]) w[i][j];
21.  
    f[i][j] = min(f[i][j],f[i][j-1] w[i][j]);
22.  
    }
23.  
    }
24.  
    }
25.  
     
26.  
    cout<<f[n][n]<<endl;
27.  
     
28.  
    return 0;
29.  
    }

3.方格取数:

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

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

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

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

思路:

同时走：分别从(1,1)出发走到终点(n, n)
同时走两条路径，令(i1,j1)分别表示两条路径所经过的点
dp[i1][j1][i2][j2] 表示所有从(1,1)走到(i1,j1)(i2,j2)路径的最大值
当i1 == i2 && j1 == j2时代表两条路径出现重复点，则只取一次a[i1][j1]的值

1.  
   #include<iostream>
2.  
   using namespace std;
3.  
   const int maxn = 30;
4.  
   int f[maxn][maxn][maxn];
5.  
   int w[maxn][maxn];
6.  
   int main(){
7.  
    
8.  
   int n;
9.  
   cin>>n;
10.  
    int a,b,c;
11.  
    while(cin>>a>>b>>c,a || b || c){
12.  
    w[a][b] =c;
13.  
    }
14.  
     
15.  
    for(int k = 2; k <= 2*n; k ) {
16.  
    for(int i1 = 1; i1 <= n; i1 ) {
17.  
    for(int i2 = 1; i2 <= n; i2 ) {
18.  
    int j1 = k-i1, j2 = k-i2;
19.  
    if(j1>=1&&j1<=n&&j2>=1&&j2<=n) {
20.  
    // 不能越界
21.  
    int &x = f[k][i1][i2];
22.  
    int t = w[i1][j1];
23.  
    if(i1!=i2) t = w[i2][j2];
24.  
    //不重合则需要加两个权重.
25.  
    x = max(x, f[k-1][i1-1][i2-1] t);
26.  
    x = max(x, f[k-1][i1-1][i2] t);
27.  
    x = max(x, f[k-1][i1][i2-1] t);
28.  
    x = max(x, f[k-1][i1][i2] t);
29.  
    //保留最大属性
30.  
    }
31.  
    }
32.  
    }
33.  
    }
34.  
     
35.  
    cout<<f[2*n][n][n];
36.  
     
37.  
    return 0;
38.  
    }

4.传纸条

小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。

一次素质拓展活动中，班上同学安排坐成一个 m 行 n 列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。

幸运的是，他们可以通过传纸条来进行交流。

纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标 (1,1)，小轩坐在矩阵的右下角，坐标 (m,n))。

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

在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。

班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙，反之亦然。 

还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用 0 表示），可以用一个 0∼100 的自然数来表示，数越大表示越好心。

小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。

现在，请你帮助小渊和小轩找到这样的两条路径。

思路:(和上一题区别在于不能走同一个格子,即  i != j 才行,而不是像上一题只加上一次)

首先考虑路径有交集该如何处理。
可以发现交集中的格子一定在每条路径的相同步数处。因此可以让两个人同时从起点出发，每次同时走一步，这样路径中相交的格子一定在同一步内。

状态表示：f[k, i, j] 表示两个人同时走了k步，第一个人在 (i, k - i) 处，第二个人在 (j, k - j)处的所有走法的最大分值。

状态计算：按照最后一步两个人的走法分成四种情况：

两个人同时向右走，最大分值是 f[k - 1, i, j] score(k, i, j)；
第一个人向右走，第二个人向下走，最大分值是 f[k - 1, i, j - 1] score(k, i, j)；
第一个人向下走，第二个人向右走，最大分值是 f[k - 1, i - 1, j] score(k, i, j)；
两个人同时向下走，最大分值是 f[k - 1, i - 1, j - 1] score(k, i, j)；
注意两个人不能走到相同格子，即i和j不能相等。

1.  
   #include <cstdio>
2.  
   #include <cstring>
3.  
   #include <iostream>
4.  
   #include <algorithm>
5.  
    
6.  
   using namespace std;
7.  
    
8.  
   const int N = 55;
9.  
    
10.  
    int n, m;
11.  
    int g[N][N];
12.  
    int f[N * 2][N][N];
13.  
     
14.  
    int main()
15.  
    {
16.  
    scanf("%d%d", &n, &m);
17.  
    for (int i = 1; i <= n; i )
18.  
    for (int j = 1; j <= m; j )
19.  
    scanf("%d", &g[i][j]);
20.  
     
21.  
    for (int k = 2; k <= n m; k )
22.  
    for (int i = max(1, k - m); i <= n && i < k; i )
23.  
    for (int j = max(1, k - m); j <= n && j < k; j )
24.  
    for (int a = 0; a <= 1; a )
25.  
    for (int b = 0; b <= 1; b )
26.  
    {
27.  
    int t = g[i][k - i];
28.  
    if (i != j || k == 2 || k == n m)//包含起点和终点
29.  
    {
30.  
    t = g[j][k - j];
31.  
    f[k][i][j] = max(f[k][i][j], f[k - 1][i - a][j - b] t);
32.  
    }
33.  
    }
34.  
     
35.  
    printf("%d\n", f[n m][n][n]);
36.  
     
37.  
    return 0;
38.  
    }
39.  
     

最长上升子序列模型

1.怪盗基德的滑翔翼

怪盗基德是一个充满传奇色彩的怪盗，专门以珠宝为目标的超级盗窃犯。

而他最为突出的地方，就是他每次都能逃脱中村警部的重重围堵，而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。

有一天，怪盗基德像往常一样偷走了一颗珍贵的钻石，不料却被柯南小朋友识破了伪装，而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。

不得已，怪盗基德只能操作受损的滑翔翼逃脱。

假设城市中一共有N幢建筑排成一条线，每幢建筑的高度各不相同。

初始时，怪盗基德可以在任何一幢建筑的顶端。

他可以选择一个方向逃跑，但是不能中途改变方向（因为中森警部会在后面追击）。

因为滑翔翼动力装置受损，他只能往下滑行（即：只能从较高的建筑滑翔到较低的建筑）。

他希望尽可能多地经过不同建筑的顶部，这样可以减缓下降时的冲击力，减少受伤的可能性。

请问，他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)？

思路:

很明显的最长上升子序列模型,而这道题求最长不上升子序列,且最开始可以在任意点,所以我们要求两次,一次顺着求,一次倒着求

1.  
   #include<iostream>
2.  
   #include<cstring>
3.  
   #include<algorithm>
4.  
   using namespace std;
5.  
   const int maxn = 110;
6.  
   int h[maxn];
7.  
   int f[maxn],r[maxn];
8.  
   int main(){
9.  
   int t;
10.  
    int n;
11.  
    cin>>t;
12.  
    while(t--){
13.  
    memset(f,0,sizeof f);
14.  
    cin>>n;
15.  
    int res=1;
16.  
    for(int i=1;i<=n;i )cin>>h[i];
17.  
    for(int i=1;i<=n;i ){
18.  
    f[i]=1;
19.  
    for(int j=1;j<i;j ){
20.  
    if(h[j]>=h[i]){
21.  
    f[i] = max(f[i],f[j] 1);
22.  
    res = max(res,f[i]);
23.  
    }
24.  
    }
25.  
    }
26.  
     
27.  
    reverse(h 1,h 1 n);
28.  
    for(int i=1;i<=n;i ){
29.  
    r[i]=1;
30.  
    for(int j=1;j<i;j ){a
31.  
    if(h[j]>=h[i]){
32.  
    r[i] = max(r[i],r[j] 1);
33.  
    res = max(res,r[i]);
34.  
    }
35.  
    }
36.  
    }
37.  
     
38.  
     
39.  
    cout<<res<<endl;
40.  
    }
41.  
     
42.  
     
43.  
     
44.  
    return 0;
45.  
    }

2.登山

五一到了，ACM队组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。

同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。

队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

思路:

其实和上一题一样,我们只用从左到右,从右到左求两遍,最后相加求最大值就行了

1.  
   #include<iostream>
2.  
   #include<cstring>
3.  
   #include<algorithm>
4.  
   using namespace std;
5.  
   const int maxn = 1010;
6.  
   int h[maxn];
7.  
   int f[maxn],r[maxn];
8.  
   int main(){
9.  
    
10.  
    int n;
11.  
    cin>>n;
12.  
    int res=0;
13.  
    for(int i=1;i<=n;i )cin>>h[i];
14.  
     
15.  
    for(int i=1;i<=n;i ){
16.  
    f[i]=1;
17.  
    for(int j=1;j<i;j ){
18.  
    if(h[j]<h[i]){
19.  
    f[i] = max(f[i],f[j] 1);
20.  
     
21.  
    }
22.  
    }
23.  
    }
24.  
     
25.  
     
26.  
     
27.  
    for(int i=n;i>=1;i--){
28.  
    r[i]=1;
29.  
    for(int j=n;j>i;j--){
30.  
    if(h[i]>h[j]){
31.  
    r[i] = max(r[i],r[j] 1);
32.  
    }
33.  
    }
34.  
    }
35.  
     
36.  
    for(int i=1;i<=n;i )res = max(res,f[i] r[i]-1);
37.  
    cout<<res<<endl;
38.  
     
39.  
     
40.  
     
41.  
    return 0;
42.  
    }

3.合唱队形

N位同学站成一排，音乐老师要请其中的 (N−K)位同学出列，使得剩下的 K位同学排成合唱队形。     

合唱队形是指这样的一种队形：设 KK 位同学从左到右依次编号为 1，2…，K，他们的身高分别为 T1，T2，…，TK，  则他们的身高满足 T1<…<Ti>Ti 1>…>TK(1≤i≤K)  

你的任务是，已知所有 N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

思路:其实和上一题一样,我们先用上面的方法找出最长符合这个条件的人数,然后用总人数减去这个数就ok了

代码就不写了

3.友好城市

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

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

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

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

思路:

1.  
   #include<iostream>
2.  
   #include<algorithm>
3.  
   #define x first
4.  
   #define y second
5.  
   using namespace std;
6.  
    
7.  
   const int maxn = 5010;
8.  
   typedef pair<int,int>pii;
9.  
   pii p[maxn];
10.  
    int f[maxn];
11.  
    int n;
12.  
    int main(){
13.  
    cin>>n;
14.  
    for(int i=1;i<=n;i ){
15.  
    int a,b;
16.  
    cin>>a>>b;
17.  
    p[i] = {a,b};
18.  
    }
19.  
    sort(p 1,p n 1);
20.  
    int res=0;
21.  
    for(int i=1;i<=n;i ){
22.  
    f[i]=1;
23.  
    for(int j=1;j<i;j ){
24.  
    if(p[i].y>p[j].y)
25.  
    f[i] = max(f[i],f[j] 1);
26.  
    res = max(res,f[i]);
27.  
    }
28.  
    }
29.  
     
30.  
    cout<<res<<endl;
31.  
    return 0;
32.  
    }

4.最长上升子序列的和

一个数的序列 bi，当 b1<b2<…<bS 的时候，我们称这个序列是上升的。

对于给定的一个序列(a1,a2,…,aN)，我们可以得到一些上升的子序列(ai1,ai2,…,aiK)，这里1≤i1<i2<…<iK≤N。

比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。

这些子序列中和最大为18，为子序列(1,3,5,9)的和。

你的任务，就是对于给定的序列，求出最大上升子序列和。

注意，最长的上升子序列的和不一定是最大的，比如序列(100,1,2,3)的最大上升子序列和为100，而最长上升子序列为(1,2,3)。

思路:

状态表示：
f[i] 表示前i个数中的最大子序列和

状态转移：
对于每一个小于a[i]的a[j] (j < i)
f[i] = max(f[i], f[j] a[i])

1.  
   #include<iostream>
2.  
   using namespace std;
3.  
   const int maxn = 1010;
4.  
   int a[maxn];
5.  
   int f[maxn];
6.  
    
7.  
   int main(){
8.  
    
9.  
   int n;
10.  
    cin>>n;
11.  
    for(int i=1;i<=n;i )cin>>a[i];
12.  
    int res=0;
13.  
    for(int i=1;i<=n;i ){
14.  
    f[i]=a[i];
15.  
    res= max(res,f[i]);
16.  
    for(int j=1;j<i;j ){
17.  
    if(a[i]>a[j]){
18.  
    f[i] = max(f[i],f[j] a[i]);
19.  
    res = max(res,f[i]);
20.  
    }
21.  
    }
22.  
    }
23.  
    cout<<res<<endl;
24.  
     
25.  
    return 0;
26.  
    }

5.导弹拦截

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。

但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

某天，雷达捕捉到敌国的导弹来袭。

由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

思路:对于第i个数来说，把它加入前 i - 1 个数构成的下降子序列组中，所有结尾元素大于第i个数的数中最小的那个数

从前往后做一遍最长下降子序列，同时维护一个数组长度为cntcnt的单调不减数组q[N]q[N]
数组 q[N] 中每个元素维护的是当前以 q[i] 结尾的下降子序列

1.  
   #include<iostream>
2.  
   using namespace std;
3.  
   const int maxn = 1010;
4.  
   int h[maxn];
5.  
   int q[maxn];//存所有最长下降子序列结尾的值
6.  
   int f[maxn];
7.  
   int main(){
8.  
   int n=1;
9.  
   while(scanf("%d",&h[n])!=-1)n ;
10.  
    //cout<<n<<endl;
11.  
    int cnt=0;
12.  
    int res = 1 ;
13.  
    for(int i=1;i<n;i ){
14.  
    f[i]=1;
15.  
    for(int j=1;j<i;j ){
16.  
    if(h[j]>=h[i])
17.  
    f[i] = max(f[i],f[j] 1);
18.  
    res = max(res,f[i]);
19.  
     
20.  
    }
21.  
    int t=1;
22.  
    while(t<=cnt&&q[t]<h[i])t ;
23.  
    q[t]=h[i];
24.  
    if(t>cnt)cnt ;
25.  
     
26.  
    }
27.  
    cout<<res<<endl;
28.  
    cout<<cnt<<endl;
29.  
     
30.  
    return 0;
31.  
    }

6. 导弹防御系统

为了对抗附近恶意国家的威胁，R 国更新了他们的导弹防御系统。

一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。

例如，一套系统先后拦截了高度为 3 和高度为 4 的两发导弹，那么接下来该系统就只能拦截高度大于 4 的导弹。

给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。

输入格式

输入包含多组测试用例。

对于每个测试用例，第一行包含整数 n，表示来袭导弹数量。

第二行包含 n个不同的整数，表示每个导弹的高度。

当输入测试用例 n=0 时，表示输入终止，且该用例无需处理。

思路:

(DFS,迭代加深,剪枝,贪心) O(n2n)O(n2n)
为了能遍历所有情况，我们首先考虑搜索顺序是什么。

搜索顺序分为两个阶段：

从前往后枚举每颗导弹属于某个上升子序列，还是下降子序列；
如果属于上升子序列，则枚举属于哪个上升子序列（包括新开一个上升子序列）；如果属于下降子序列，可以类似处理。
因此可以仿照AcWing 896. 最长上升子序列 II，分别记录当前每个上升子序列的末尾数up[]，和下降子序列的末尾数down[]。这样在枚举时可以快速判断当前数是否可以接在某个序列的后面。

注意这里的记录方式和上一题稍有不同：

这里是记录每个子序列末尾的数；
上一题是记录每种长度的子序列的末尾最小值。
此时搜索空间仍然很大，因此该如何剪枝呢？

对于第二阶段的枚举，我们可以仿照上一题的贪心方式，对于上升子序列而言，我们将当前数接在最大的数后面，一定不会比接在其他数列后面更差。
这是因为处理完当前数后，一定出现一个以当前数结尾的子序列，这是固定不变的，那么此时其他子序列的末尾数越小越好。

注意到按照这种贪心思路，up[]数组和down[]数组一定是单调的，因此在遍历时找到第一个满足的序列后就可以直接break了。

1.  
   #include <cstring>
2.  
   #include <iostream>
3.  
   #include <algorithm>
4.  
    
5.  
   using namespace std;
6.  
    
7.  
   const int N = 60;
8.  
    
9.  
   int n;
10.  
    int h[N];
11.  
    int up[N], down[N];
12.  
     
13.  
    bool dfs(int depth, int u, int su, int sd)
14.  
    {
15.  
    // 如果上升序列个数 下降序列个数 > 总个数是上限，则回溯
16.  
    if (su sd > depth) return false;
17.  
    if (u == n) return true;
18.  
     
19.  
    // 枚举放到上升子序列中的情况
20.  
    bool flag = false;
21.  
    for (int i = 1; i <= su; i )
22.  
    if (up[i] < h[u])
23.  
    {
24.  
    int t = up[i];
25.  
    up[i] = h[u];
26.  
    if (dfs(depth, u 1, su, sd)) return true;
27.  
    up[i] = t;
28.  
    flag = true;
29.  
    break; // 注意由上述证明的贪心原理，只要找到第一个可以放的序列，就可以结束循环了
30.  
    }
31.  
    if (!flag) // 如果不能放到任意一个序列后面，则单开一个新的序列
32.  
    {
33.  
    up[su 1] = h[u];
34.  
    if (dfs(depth, u 1, su 1, sd)) return true;
35.  
    }
36.  
     
37.  
    // 枚举放到下降子序列中的情况
38.  
    flag = false;
39.  
    for (int i = 1; i <= sd; i )
40.  
    if (down[i] > h[u])
41.  
    {
42.  
    int t = down[i];
43.  
    down[i] = h[u];
44.  
    if (dfs(depth, u 1, su, sd)) return true;
45.  
    down[i] = t;
46.  
    flag = true;
47.  
    break; // 注意由上述证明的贪心原理，只要找到第一个可以放的序列，就可以结束循环了
48.  
    }
49.  
    if (!flag) // 如果不能放到任意一个序列后面，则单开一个新的序列
50.  
    {
51.  
    down[sd 1] = h[u];
52.  
    if (dfs(depth, u 1, su, sd 1)) return true;
53.  
    }
54.  
     
55.  
    return false;
56.  
    }
57.  
     
58.  
    int main()
59.  
    {
60.  
    while (cin >> n, n)
61.  
    {
62.  
    for (int i = 0; i < n; i ) cin >> h[i];
63.  
     
64.  
    int depth = 0;
65.  
    while (!dfs(depth, 0, 0, 0)) depth ; // 迭代加深搜索
66.  
     
67.  
    cout << depth << endl;
68.  
    }
69.  
     
70.  
    return 0;
71.  
    }
72.  
     
73.  
    作者：yxc
74.  
    链接：https://www.acwing.com/solution/content/4258/
75.  
    来源：AcWing
76.  
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

7. 最长公共上升子序列

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。

小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。

小沐沐说，对于两个数列 A 和 B，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。

奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。

不过，只要告诉奶牛它的长度就可以了。

数列 A 和 B 的长度均不超过 3000。

思路:

闫氏DP分析法：(结合了LCS与LIS的状态表示的方法，可以很直接的发现二者的影子)
状态表示 f[i][j]—集合：考虑 a 中前 i 个数字，b 中前 j 个数字 ，且当前以 b[j] 结尾的子序列的方案

状态表示 f[i][j]—属性：该方案的子序列长度最大 max
状态转移 ：

从考虑 a数组 中前 i-1 个数字， b数组 中前 j 个数字 ，且当前以 b[j] 结尾的子序列的方案转移过来：
fi,j=max(fi,j,fi−1,j)

从考虑 a数组 中前 i 个数字， b数组 中前 k 个数字 ，且当前以 b[k] 结尾的子序列的方案转移过来：
fi,j=max(fi,j,fi−1,k 1)k∈[0,j−1],ai=bj,bj>bk
初始状态：f[0][0]

目标状态：f[n][i]

集合划分:

背包模型:

01背包:

1.采药

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。

为此，他想拜附近最有威望的医师为师。

医师为了判断他的资质，给他出了一个难题。

医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

1.  
   #include<iostream>
2.  
   using namespace std;
3.  
   const int maxn = 1010;
4.  
   int f[maxn];
5.  
   int w[maxn][maxn];
6.  
   int v[maxn][maxn];
7.  
   int main(){
8.  
   int t,m;
9.  
   cin>>t>>m;
10.  
    for(int i=1;i<=m;i ){
11.  
    int w,v;
12.  
    cin>>w>>v;
13.  
    for(int j=t;j>=w;j--){
14.  
    f[j] = max(f[j],f[j-w] v);
15.  
    }
16.  
    }
17.  
     
18.  
    cout<<f[t]<<endl;
19.  
     
20.  
    return 0;
21.  
    }

2.装箱问题

有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积（正整数）。

要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

思路:和上一题一样其实,只要找到最大值就可以了

1.  
   #include<iostream>
2.  
   using namespace std;
3.  
   const int maxn = 1e5 10;
4.  
   int f[maxn];
5.  
   int w[maxn];
6.  
    
7.  
   int main(){
8.  
   int v;
9.  
   cin>>v;
10.  
     
11.  
    int n;
12.  
    cin>>n;
13.  
    for(int i=1;i<=n;i ){
14.  
    int V;
15.  
    cin>>V;
16.  
    for(int j=v;j>=V;j--){
17.  
    f[j] = max(f[j],f[j-V] V);
18.  
     
19.  
    }
20.  
    }
21.  
     
22.  
    cout<<v-f[v]<<endl;
23.  
    return 0;
24.  
    }

3.宠物小精灵之收服

宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。

一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。

小智也想收服其中的一些小精灵。

然而，野生的小精灵并不那么容易被收服。

对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。

当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。

当小智的精灵球用完时，狩猎也宣告结束。

我们假设小智遇到野生小精灵时有两个选择：收服它，或者离开它。

如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害；如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。

小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。

现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。

请问，小智该如何选择收服哪些小精灵以达到他的目标呢？

思路:

1.  
   #include<iostream>
2.  
   using namespace std;
3.  
   const int maxn = 1010;
4.  
   int f[maxn][maxn];
5.  
   int v1[maxn],v2[maxn];
6.  
    
7.  
   int main(){
8.  
    
9.  
    
10.  
    int m,k,n;
11.  
    cin>>m>>k>>n;
12.  
    for (int i = 1; i <= n; i) cin >> v1[i] >> v2[i];
13.  
     
14.  
    for(int i=1;i<=n;i ){
15.  
     
16.  
    for(int j=m;j>=v1[i];j--){
17.  
    for(int t=k-1;t>=v2[i];t--){
18.  
    f[j][t] = max(f[j][t],f[j-v1[i]][t-v2[i]] 1);
19.  
    }
20.  
    }
21.  
    }
22.  
    cout<<f[m][k-1]<<" ";
23.  
    int t=0;
24.  
    for(int i=0;i<=k-1;i ){
25.  
    if(f[m][i]==f[m][k-1]){
26.  
    t = i;
27.  
    break;
28.  
    }
29.  
    }
30.  
    cout<<k-t<<endl;
31.  
    return 0;
32.  
    }

3.数字组合

给定 N个正整数 A1,A2,…,AN，从中选出若干个数，使它们的和为 M，求有多少种选择方案

思路:

1.  
   #include<iostream>
2.  
   using namespace std;
3.  
   const int maxn = 110;
4.  
   int a[maxn];
5.  
   int f[maxn][100010];
6.  
   int main(){
7.  
   int n,m;
8.  
   cin>>n>>m;
9.  
   for(int i=1;i<=n;i )cin>>a[i];
10.  
    f[0][0]=1;
11.  
    for(int i=1;i<=n;i ){
12.  
    for(int j=0;j<=m;j ){
13.  
    f[i][j] = f[i-1][j];
14.  
    if(j>=a[i])f[i][j] =f[i-1][j-a[i]];
15.  
    }
16.  
    }
17.  
     
18.  
    cout<<f[n][m];
19.  
     
20.  
    return 0;
21.  
    }

完全背包:

4.买书

小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。

问小明有多少种买书方案？（每种书可购买多本）

思路:

可以买多本,可见是完全背包

1.  
   #include<iostream>
2.  
   using namespace std;
3.  
    
4.  
   const int maxn = 1010;
5.  
   int f[maxn][maxn];
6.  
   int a[5] = {0,10,20,50,100};
7.  
    
8.  
   int main(){
9.  
   int n;
10.  
    cin>>n;
11.  
    f[0][0]=1;
12.  
    for(int i=1;i<=4;i ){
13.  
    for(int j = 0;j<=n;j ){
14.  
    f[i][j] =f[i-1][j];
15.  
    if(j>=a[i])f[i][j] =f[i][j-a[i]];
16.  
    }
17.  
    }
18.  
    cout<<f[4][n];
19.  
    return 0;
20.  
    }

5.货币系统

给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。

思路:和上一题一样

1.  
   #include<iostream>
2.  
   using namespace std;
3.  
   const int maxn = 1e7 10;
4.  
   typedef long long ll;
5.  
   ll f[20][maxn];
6.  
   int a[maxn];
7.  
    
8.  
   int n,m;
9.  
    
10.  
    int main(){
11.  
     
12.  
    cin>>n>>m;
13.  
    f[0][0]=1;
14.  
    for(int i=1;i<=n;i ){
15.  
    ll v;
16.  
    cin>>v;
17.  
    for(ll j = 0;j<=m;j ){
18.  
    f[i][j] =f[i-1][j];
19.  
    if(j>=v)f[i][j] =f[i][j-v];
20.  
    }
21.  
    }
22.  
    cout<<f[n][m];
23.  
     
24.  
    return 0;
25.  
    }

6.货币系统(完全背包求解最大无关向量组个数)

在网友的国度中共有 n 种不同面额的货币，第 i 种货币的面额为 a[i]，你可以假设每一种货币都有无穷多张。

为了方便，我们把货币种数为 n、面额数组为 a[1..n] 的货币系统记作 (n,a)。 

在一个完善的货币系统中，每一个非负整数的金额 x 都应该可以被表示出，即对每一个非负整数 x，都存在 n 个非负整数 t[i] 满足 a[i]×t[i] 的和为 x。

然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额 x 不能被该货币系统表示出。

例如在货币系统 n=3, a=[2,5,9] 中，金额 1,3 就无法被表示出来。 

两个货币系统 (n,a) 和 (m,b) 是等价的，当且仅当对于任意非负整数 x，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。 

现在网友们打算简化一下货币系统。

他们希望找到一个货币系统 (m,b)，满足 (m,b) 与原来的货币系统 (n,a) 等价，且 m 尽可能的小。

他们希望你来协助完成这个艰巨的任务：找到最小的 m。

(n,a)和(m,b)等价⇔∀k∈Z ，{k如果能被a线性表出，则k也能被b线性表出,k如果不能被a线性表出，则k也不能被b线性表出

现给定 货币系统 (n,a)(n,a)，求一个 等价 的 货币系统 (m,b)(m,b) ，要求 mm 尽可能最小

如何求向量组 (a1,a2,⋯,an)(a1,a2,⋯,an) 的 最大无关向量组
我们可以利用到 数论 中 埃式筛法 的思想：

对于一个 无效的 元素 aiai，他只会被 小于 他的元素的 线性组合 表出，满足该要求的 aiai 就要被 筛掉

所以我们要先 排序

而我们在做 完全背包 的时候，需要求出所有恰好能被前 ii 个物品选出的体积的方案

即就是在 完全背包 求方案数的过程中，统计那些 初始不能被满足 的物品体积 个数

这就是我们在 AcWing 1021. 货币系统 中所使用的 DP模型

那一题我们求解的是方案数，这题稍微改一下，改成这种方案能否被满足即可，具体如下:

AcWing 532. 货币系统【完全背包求解最大无关向量组个数】 - AcWing

1.  
   #include <iostream>
2.  
   #include <cstring>
3.  
   #include <algorithm>
4.  
    
5.  
   using namespace std;
6.  
    
7.  
   //这题是一道线性代数问题
8.  
   //求解一个向量组的秩(最大无关向量组的向量个数)
9.  
   //但是代码写起来就是一个模拟筛的过程
10.  
    //从小到大，先查看当前数有没有被晒掉，
11.  
    //1)如果没有就把它加入到最大无关向量组中，并把他以及他和此前的硬币的线性组合都筛掉
12.  
    //2)如果有就不理会
13.  
    //即就是在完全背包求方案数的过程中，统计那些初始没有方案数的物品
14.  
    //这样就变成一个完全背包问题了
15.  
     
16.  
    const int N = 110, M = 25010;
17.  
    int n;
18.  
    int v[N];
19.  
    bool f[M];
20.  
     
21.  
    int main()
22.  
    {
23.  
    int T = 1;
24.  
    cin >> T;
25.  
    while (T -- )
26.  
    {
27.  
    cin >> n;
28.  
    for (int i = 1; i <= n; i) cin >> v[i];
29.  
    sort(v 1, v n 1);//排序的原因见之前的分析
30.  
     
31.  
    //我们只需统计所有物品的体积是否能被其他的线性表出
32.  
    //因此背包的体积只需设置为最大的物品体积即可
33.  
    //res用来记录最大无关向量组的个数
34.  
    int m = v[n], res = 0;
35.  
    memset(f, 0, sizeof f);
36.  
    f[0] = true; //状态的初值
37.  
    for (int i = 1; i <= n; i)
38.  
    {
39.  
    //如果当前物品体积被之前的物品组合线性筛掉了，则它是无效的
40.  
    if (f[v[i]]) continue;
41.  
    //如果没有被筛掉，则把它加入最大无关向量组
42.  
    res ;
43.  
    //筛掉当前最大无关向量组能线性表示的体积
44.  
    for (int j = v[i]; j <= m; j)
45.  
    {
46.  
    f[j] |= f[j - v[i]];
47.  
    }
48.  
    }
49.  
    //输出最大无关向量组的向量个数
50.  
    cout << res << endl;
51.  
    }
52.  
    return 0;
53.  
    }
54.  
     
55.  
    作者：彩色铅笔
56.  
    链接：https://www.acwing.com/solution/content/53198/
57.  
    来源：AcWing
58.  
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

7.多重背包问题三

8.庆功会(多重背包)

为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。

期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。

思路:

1.  
   #include<iostream>
2.  
   using namespace std;
3.  
   const int maxn = 2e5 10;
4.  
   int f[maxn];
5.  
   int v[maxn];
6.  
   int w[maxn];
7.  
    
8.  
   int main(){
9.  
   int n,m;
10.  
    cin>>n>>m;
11.  
    int cnt = 0 ;
12.  
    for(int i=0;i<n;i ){
13.  
    int V,W,S;
14.  
    cin>>V>>W>>S;
15.  
    int k=1;
16.  
    while(k<=S){
17.  
    cnt;
18.  
    v[cnt] = k*V;
19.  
    w[cnt] = k*W;
20.  
    S-=k;
21.  
    k*=2;
22.  
     
23.  
    }
24.  
    if(S){
25.  
    cnt;
26.  
    v[cnt] = S*V;
27.  
    w[cnt] = S*W;
28.  
    }
29.  
     
30.  
    }
31.  
     
32.  
    for(int i=1;i<=cnt;i ){
33.  
    for(int j = m;j>=v[i];j--){
34.  
    f[j] = max(f[j],f[j-v[i]] w[i]);
35.  
    }
36.  
    }
37.  
    cout<<f[m]<<endl;
38.  
     
39.  
    return 0;
40.  
    }

9.混合背包:

有 N 种物品和一个容量是 V 的背包。

物品一共有三类：

第一类物品只能用1次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用 si 次（多重背包）；
每种体积是 vi，价值是 wi。

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

1.  
   #include <iostream>
2.  
    
3.  
   using namespace std;
4.  
    
5.  
   const int N = 1010;
6.  
    
7.  
   int n, m;
8.  
   int v[N], w[N], s[N];
9.  
   int f[N];
10.  
     
11.  
    int main()
12.  
    {
13.  
    cin >> n >> m;
14.  
    for (int i = 1; i <= n; i) cin >> v[i] >> w[i] >> s[i];
15.  
     
16.  
    for (int i = 1; i <= n; i)
17.  
    {
18.  
    //完全背包
19.  
    if (!s[i])
20.  
    {
21.  
    for (int j = v[i]; j <= m; j)
22.  
    {
23.  
    f[j] = max(f[j], f[j - v[i]] w[i]);
24.  
    }
25.  
    }
26.  
    else
27.  
    {
28.  
    //把多重背包用二进制优化
29.  
    //这样就变成做多个01背包了
30.  
    if (s[i] == -1) s[i] = 1;
31.  
    //二进制优化
32.  
    for (int k = 1; k <= s[i]; k *= 2)
33.  
    {
34.  
    for (int j = m; j >= k * v[i]; -- j)
35.  
    {
36.  
    f[j] = max(f[j], f[j - k * v[i]] k * w[i]);
37.  
    }
38.  
    s[i] -= k;
39.  
    }
40.  
    if (s[i])
41.  
    {
42.  
    for (int j = m; j >= s[i] * v[i]; -- j)
43.  
    {
44.  
    f[j] = max(f[j], f[j - s[i] * v[i]] s[i] * w[i]);
45.  
    }
46.  
    }
47.  
    }
48.  
    }
49.  
     
50.  
    cout << f[m] << endl;
51.  
     
52.  
    return 0;
53.  
    }
54.  
     

 10.二维费用的背包问题

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。

每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。

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

思路:

1.  
   #include<iostream>
2.  
   using namespace std;
3.  
    
4.  
   const int maxn = 1010;
5.  
   int f[maxn][maxn];
6.  
    
7.  
   int main(){
8.  
    
9.  
    
10.  
    int n,v,m;
11.  
    cin>>n>>v>>m;
12.  
    for(int i=1;i<=n;i ){
13.  
    int a,b,c;
14.  
    cin>>a>>b>>c;
15.  
    for(int j=v;j>=a;j--){
16.  
    for(int k=m;k>=b;k--){
17.  
    f[j][k] = max(f[j][k],f[j-a][k-b] c);
18.  
    }
19.  
    }
20.  
    }
21.  
    cout<<f[v][m];
22.  
    return 0;
23.  
    }

11.潜水员:

潜水员为了潜水要使用特殊的装备。

他有一个带2种气体的气缸：一个为氧气，一个为氮气。

让潜水员下潜的深度需要各种数量的氧和氮。

潜水员有一定数量的气缸。

每个气缸都有重量和气体容量。

潜水员为了完成他的工作需要特定数量的氧和氮。

他完成工作所需气缸的总重的最低限度的是多少？

例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：

1.  
   3 36 120
2.  
    
3.  
   10 25 129
4.  
    
5.  
   5 50 250
6.  
    
7.  
   1 45 130
8.  
    
9.  
   4 20 119

如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。

你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。

思路:

1.  
   #include <iostream>
2.  
   #include <cstring>
3.  
    
4.  
   using namespace std;
5.  
    
6.  
   const int N = 1010, M = 85;
7.  
    
8.  
   int n, m, t;
9.  
    
10.  
    int v1[N], v2[N], w[N];
11.  
    int f[M][M];
12.  
     
13.  
    int main()
14.  
    {
15.  
    cin >> n >> m >> t;
16.  
    for (int i = 1; i <= t; i) cin >> v1[i] >> v2[i] >> w[i];
17.  
     
18.  
    memset(f, 0x3f, sizeof f); //求最小值要把除初始状态以外的所有状态初始化为 ∞
19.  
    f[0][0] = 0; //这里我们把所有j,k小于0的初始状态都合并到f[0][0][0]中来转移,也就是下面的max操作
20.  
    for (int i = 1; i <= t; i)
21.  
    {
22.  
    for (int j = n; j >= 0; -- j)
23.  
    {
24.  
    for (int k = m; k >= 0; -- k)
25.  
    {
26.  
    f[j][k] = min(f[j][k], f[max(j - v1[i], 0)][max(k - v2[i], 0)] w[i]);
27.  
    }
28.  
    }
29.  
    }
30.  
    cout << f[n][m] << endl;
31.  
    return 0;
32.  
    }
33.  
     

12.机器分配

总公司拥有M台 相同 的高效设备，准备分给下属的N个分公司。

各分公司若获得这些设备，可以为国家提供一定的盈利。盈利与分配的设备数量有关。

问：如何分配这M台设备才能使国家得到的盈利最大？

求出最大盈利值。

分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。

思路:

1.  
   #include <iostream>
2.  
    
3.  
   using namespace std;
4.  
    
5.  
   const int N = 20;
6.  
    
7.  
   int n, m;
8.  
   int w[N][N];
9.  
   int f[N][N];
10.  
    int path[N], cnt;
11.  
     
12.  
    void dfs(int i, int j)
13.  
    {
14.  
    if (!i) return;
15.  
    //寻找当前状态f[i][j]是从上述哪一个f[i-1][k]状态转移过来的
16.  
    for (int a = 0; a <= j; a)
17.  
    {
18.  
    if (f[i - 1][j - a] w[i][a] == f[i][j])
19.  
    {
20.  
    path[cnt ] = a;
21.  
    dfs(i - 1, j - a);
22.  
    return;
23.  
    }
24.  
    }
25.  
    }
26.  
    int main()
27.  
    {
28.  
    //input
29.  
    cin >> n >> m;
30.  
    for (int i = 1; i <= n; i)
31.  
    for (int j = 1; j <= m; j)
32.  
    cin >> w[i][j];
33.  
     
34.  
    //dp
35.  
    for (int i = 1; i <= n; i)
36.  
    for (int j = 1; j <= m; j)
37.  
    for (int k = 0; k <= j; k)
38.  
    f[i][j] = max(f[i][j], f[i - 1][j - k] w[i][k]);
39.  
    cout << f[n][m] << endl;
40.  
     
41.  
    //find path
42.  
    dfs(n, m);
43.  
    for (int i = cnt - 1, id = 1; i >= 0; -- i, id)
44.  
    cout << id << " " << path[i] << endl;
45.  
    return 0;
46.  
    }
47.  
     

13.开心的金明

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。

更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 NN 元钱就行”。

今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 NN 元。

于是，他把每件物品规定了一个重要度，分为 55 等：用整数 1∼51∼5 表示，第 55 等最重要。

他还从因特网上查到了每件物品的价格（都是整数元）。

他希望在不超过 NN 元（可以等于 NN 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 

设第 jj 件物品的价格为 v[j]v[j]，重要度为 w[j]w[j]，共选中了 kk 件物品，编号依次为 j1，j2，…，jkj1，j2，…，jk，则所求的总和为： 

v[j1]×w[j1] v[j2]×w[j2] … v[jk]×w[jk]v

请你帮助金明设计一个满足要求的购物单。

思路:01背包

1.  
   #include<iostream>
2.  
   using namespace std;
3.  
   const int maxn = 1e5 10;
4.  
   int f[maxn];
5.  
   int main(){
6.  
   int n,m;
7.  
   cin>>n>>m;
8.  
    
9.  
   for(int i=1;i<=m;i ){
10.  
    int v,w;
11.  
    cin>>v>>w;
12.  
    for(int j = n;j>=v;j--){
13.  
    f[j] = max(f[j],f[j-v] w*v);
14.  
    }
15.  
    }
16.  
     
17.  
    cout<<f[n];
18.  
     
19.  
    return 0;
20.  
    }

14.有依赖的背包问题

 N个物品和一个容量是 V 的背包。

物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。

如下图所示：

如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。

每件物品的编号是 ii，体积是 vivi，价值是 wi，依赖的父节点编号是 pi。物品的下标范围是 1…N。

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

输出最大价值。

1.  
   #include <iostream>
2.  
   #include <cstring>
3.  
    
4.  
   using namespace std;
5.  
    
6.  
   const int N = 110;
7.  
    
8.  
   int n, m, root;
9.  
   int h[N], e[N], ne[N], idx;
10.  
    int v[N], w[N];
11.  
    int f[N][N];
12.  
     
13.  
     
14.  
    void add(int a, int b)
15.  
    {
16.  
    e[idx] = b, ne[idx] = h[a], h[a] = idx ;
17.  
    }
18.  
    void dfs(int u)
19.  
    {
20.  
    //先枚举所有状态体积小于等于j-v[u]的所有子节点们能够获得的最大价值
21.  
    for (int i = h[u]; ~i; i = ne[i])
22.  
    {
23.  
    int son = e[i];
24.  
    dfs(son); //从下往上算，先计算子节点的状态
25.  
    for (int j = m - v[u]; j >= 0; -- j) //枚举所有要被更新的状态
26.  
    {
27.  
    for (int k = 0; k <= j; k) //枚举该子节点在体积j下能使用的所有可能体积数
28.  
    {
29.  
    f[u][j] = max(f[u][j], f[u][j - k] f[son][k]);
30.  
    }
31.  
    }
32.  
    }
33.  
    //最后选上第u件物品
34.  
    for (int j = m; j >= v[u]; -- j) f[u][j] = f[u][j - v[u]] w[u];
35.  
    for (int j = 0; j < v[u]; j) f[u][j] = 0; //清空没选上u的所有状态
36.  
    }
37.  
    int main()
38.  
    {
39.  
    memset(h, -1, sizeof h);
40.  
    cin >> n >> m;
41.  
    for (int i = 1; i <= n; i)
42.  
    {
43.  
    int p;
44.  
    cin >> v[i] >> w[i] >> p;
45.  
    if (p == -1) root = i;
46.  
    else add(p, i);
47.  
    }
48.  
    dfs(root);
49.  
    cout << f[root][m] << endl;
50.  
    return 0;
51.  
    }
52.  
     
53.  
    作者：彩色铅笔
54.  
    链接：https://www.acwing.com/solution/content/54139/
55.  
    来源：AcWing
56.  
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

15.背包问题求方案数

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

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

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

输出 最优选法的方案数。注意答案可能很大，请输出答案模 1e9 7的结果。

思路:

1.  
   #include<iostream>
2.  
    
3.  
   using namespace std;
4.  
    
5.  
   const int N = 1010;
6.  
   const int mod = 1e9 7;
7.  
    
8.  
   int f[N], cnt[N];
9.  
   int main()
10.  
    {
11.  
    int n, m;
12.  
    scanf("%d%d", &n, &m);
13.  
    for(int i = 0; i <= m; i ) cnt[i] = 1;
14.  
     
15.  
    for(int i = 1; i <= n; i )
16.  
    {
17.  
    int v, w;
18.  
    scanf("%d%d", &v, &w);
19.  
    for(int j = m; j >= v; j --)
20.  
    {
21.  
    int value = f[j - v] w;
22.  
    if(value > f[j])
23.  
    {
24.  
    f[j] = value;
25.  
    cnt[j] = cnt[j - v];
26.  
    }else if(value == f[j]){
27.  
    cnt[j] = (cnt[j] cnt[j - v]) % mod;
28.  
    }
29.  
    }
30.  
    }
31.  
     
32.  
    printf("%d", cnt[m]);
33.  
    return 0;
34.  
    }
35.  
     
36.  
    作者：滑稽_ωﾉ
37.  
    链接：https://www.acwing.com/solution/content/3999/
38.  
    来源：AcWing
39.  
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

16.背包问题求具体方案

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

第 ii 件物品的体积是 vi，价值是 wi。

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

输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。

思路:

1.  
   #include<iostream>
2.  
   using namespace std;
3.  
    
4.  
   const int maxn = 1010;
5.  
    
6.  
   int f[maxn][maxn];
7.  
   int v[maxn],w[maxn];
8.  
   int main(){
9.  
   int n,m;
10.  
    cin>>n>>m;
11.  
    for(int i=1;i<=n;i ){
12.  
    cin>>v[i]>>w[i];
13.  
    }
14.  
     
15.  
    for(int i=n;i>=1;i--){
16.  
    for(int j=0;j<=m;j ){
17.  
    f[i][j] = f[i 1][j];
18.  
    if(j>=v[i]) f[i][j] = max(f[i][j],f[i 1][j-v[i]] w[i]);
19.  
    }
20.  
    }
21.  
    int j = m;
22.  
    for(int i=1;i<=n;i ){
23.  
    if(j>=v[i]&&f[i][j]==f[i 1][j-v[i]] w[i]){
24.  
    cout<<i<<" ";
25.  
    j-=v[i];
26.  
    }
27.  
    }
28.  
    }

状态机模型

 1大盗阿福

阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。

这条街上一共有 N 家店铺，每家店中都有一些现金。

阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。

作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。

他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？

思路:

1.  
   #include<iostream>
2.  
   using namespace std;
3.  
   const int maxn = 1e5 10;
4.  
   int f[maxn][2];
5.  
   int w[maxn];
6.  
   int main(){
7.  
   int t;
8.  
   cin>>t;
9.  
   while(t--){
10.  
    int n;
11.  
    cin>>n;
12.  
    f[0][1]=-0x3f3f3f3f;
13.  
    f[0][0]=0;
14.  
    for(int i=1;i<=n;i )cin>>w[i];
15.  
     
16.  
    for(int i=1;i<=n;i ){
17.  
    f[i][0] = max(f[i-1][0],f[i-1][1]);
18.  
    f[i][1] = f[i-1][0] w[i];
19.  
    }
20.  
    cout<<max(f[n][0],f[n][1])<<endl;
21.  
    }
22.  
     
23.  
     
24.  
     
25.  
    return 0;
26.  
    }

2.股票买卖 IV

给定一个长度为 N 的数组，数组中的第 i个数字表示一个给定股票在第 i天的价格。

设计一个算法来计算你所能获取的最大利润，你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。一次买入卖出合为一笔交易。

思路:

1.  
   #include<iostream>
2.  
   #include<cstring>
3.  
   using namespace std;
4.  
   const int maxn = 1e5 10;
5.  
   int f[maxn][110][2];
6.  
   int w[maxn];
7.  
    
8.  
   int main(){
9.  
   int n,k;
10.  
    cin>>n>>k;
11.  
    memset(f,-0x3f,sizeof f);
12.  
    for(int i=1;i<=n;i )cin>>w[i];
13.  
    for (int i = 0; i <= n; i ) f[i][0][0] = 0;
14.  
    for(int i=1;i<=n;i ){
15.  
    for(int j= 1;j<=k;j ){
16.  
    f[i][j][0] = max(f[i-1][j][0],f[i-1][j][1] w[i]);
17.  
    f[i][j][1] = max(f[i-1][j-1][0]-w[i],f[i-1][j][1]);
18.  
    }
19.  
    }
20.  
    int res=0;
21.  
    for(int i=0;i<=k;i ){
22.  
    res = max(res,f[n][i][0]);
23.  
    }
24.  
    cout<<res<<endl;
25.  
     
26.  
    return 0;
27.  
    }

3.股票买卖 V

给定一个长度为 N的数组，数组中的第 i 个数字表示一个给定股票在第 i天的价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

思路:

1.  
   #include<iostream>
2.  
   #include<cstring>
3.  
   using namespace std;
4.  
   const int maxn = 1e5 10;
5.  
   int f[maxn][3];
6.  
   int w[maxn];
7.  
   int main(){
8.  
   int n;
9.  
   cin>>n;
10.  
    memset(f,-0x3f,sizeof f);
11.  
    f[0][2]=0;
12.  
     
13.  
    for(int i=1;i<=n;i )cin>>w[i];
14.  
     
15.  
    for(int i=1;i<=n;i ){
16.  
    f[i][0] = max(f[i-1][0],f[i-1][2]-w[i]);
17.  
    f[i][1] = f[i-1][0] w[i];
18.  
    f[i][2] = max(f[i-1][1],f[i-1][2]);
19.  
    }
20.  
     
21.  
    cout<<max(f[n][1],f[n][2]);
22.  
     
23.  
     
24.  
    return 0;
25.  
    }

4.密码设计(还没懂,后期补上)

5.修复DNA

状态压缩dp

1.小国王

在 n×n的棋盘上放 k 个国王，国王可攻击相邻的 8个格子，求使它们无法互相攻击的方案总数。

思路：

这道题目，根据数据范围，不难得出，这道题目考察的是状态压缩动态规划。

分析题目，我们可以得到如下信息。

一个点的相邻八格，不可以有其他点。
棋盘置点类型。
那么，我们接下来，思考两个流程。

如何表示状态

表示状态
显然，题目给的条件，是国王总数是严格限制的，就是k个。

所以说，我们放置了多少个国王，是需要考虑的。

接着，根据棋盘类型的状态压缩动态规划的套路，每一行的状态，我们需要明白。

也就是每一行，哪些位置放了国王。

综上所述，我们可以得出，动态规划的状态表示。

f[i][j][s]为所有只摆在前i行，目前摆了j个国王，而且第i行的摆放状态为s

我们可以举一个例子

n=5f[1][2][20]表示第一行，已经摆了两个国王，摆在左边第一个，和左边第三个(20)10=(10100)2
状态转移
在这里，状态之间的转移，必然要满足，国王之间不会相互攻击到，那么我们进行分析。

两个国王，如果他们存在，直接靠近（上下左右）或者简介靠近（两斜对角），那么显然是不合法的。

因此，转换成为状态理解。

对于一个状态集合而言，显然不能存在相邻的1.
101(可以)两个国王有间隔110(不可以)国王1和国王2相邻，可以相互攻击
 

因为这会导致，左右两个国王相邻，然后发起攻击。

而且，对于上下两行而言，不能有共同的一位有1

101101
 

因为这会导致，上下两个国王相邻，然后发起攻击。

我们讨论完了，上下左右，接下来是最难的两斜对角。
我们设，第i行的状态为a，第i 1行状态为b
 

那么
S=a或b 也就是S=a|b
 

是不可以存在，有相邻的1的。
a=100   b=010      S=110
 

因此这会导致，两斜对角国王相互攻击。

综上所述，我们得到集合转移的约束条件。

1.  
    
2.  
    
3.  
   #include<iostream>
4.  
   #include<vector>
5.  
   using namespace std;
6.  
    
7.  
   const int maxn = 1e4 10;
8.  
   vector<int>head[1<<11];
9.  
   int cnt[maxn];
10.  
    typedef long long ll;
11.  
    ll f[12][110][1<<11];
12.  
    vector<int>state;
13.  
    int n,k;
14.  
    //是否有相邻的一
15.  
    int check(int x){
16.  
    return !(x&(x>>1));
17.  
    }
18.  
    //处理出有多少个一
19.  
    int count(int x){
20.  
    int res=0;
21.  
    for(int i=0;i<n;i )res =x>>i&1;
22.  
    return res;
23.  
    }
24.  
     
25.  
    int main(){
26.  
    cin>>n>>k;
27.  
    //处理出所有合法状态
28.  
    for(int i=0;i<1<<n;i ){
29.  
    if(check(i)){
30.  
    state.push_back(i);
31.  
    cnt[i] = count(i);
32.  
    }
33.  
    }
34.  
     
35.  
    //处理出每个状态能过转移到哪一些状态
36.  
    for(auto a:state){
37.  
    for(auto b: state){
38.  
    if(!(a&b)&&(check(a|b)))head[a].push_back(b);
39.  
     
40.  
    }
41.  
    }
42.  
     
43.  
    f[0][0][0]=1;
44.  
    for(int i=1;i<=n;i ){
45.  
    for(int j=0;j<=k;j ){
46.  
    for(auto &a:state){
47.  
    for(auto &b:head[a]){
48.  
     
49.  
    if(j-cnt[a]>=0){
50.  
    f[i][j][a] = f[i-1][j-cnt[a]][b];
51.  
    }
52.  
    }
53.  
    }
54.  
    }
55.  
    }
56.  
    ll res=0;
57.  
    for(auto a:state)res =f[n][k][a];
58.  
    cout<<res<<endl;
59.  
    return 0;
60.  
    }

2.玉米田

农夫约翰的土地由 M×N个小方格组成，现在他要在土地里种植玉米。

非常遗憾，部分土地是不育的，无法种植。

而且，相邻的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。

现在给定土地的大小，请你求出共有多少种种植方法。

土地上什么都不种也算一种方法。

思路：

1.  
    
2.  
   #include<iostream>
3.  
   #include<vector>
4.  
    
5.  
   using namespace std;
6.  
   const int mod = 1e8;
7.  
   vector<int>state;
8.  
   vector<int>head[1<<14];
9.  
   int g[14];//用来存图
10.  
    int f[14][1<<14];//第i行状态为j的方案
11.  
    int check(int x){
12.  
    return !(x&(x>>1));
13.  
    }
14.  
    int main(){
15.  
    int m,n;
16.  
    cin>>m>>n;
17.  
    //存图
18.  
    for(int i=1;i<=m;i ){
19.  
    for(int j=0;j<n;j ){
20.  
    int x;
21.  
    cin>>x;
22.  
    g[i] |= (!x)<<j;
23.  
    }
24.  
    }
25.  
    //处理出所有合法状态
26.  
    for(int i = 0;i<1<<n;i ){
27.  
    if(check(i))state.push_back(i);
28.  
    }
29.  
    //处理出所有状态能够转移到的状态
30.  
    for(auto a : state){
31.  
    for(auto b: state){
32.  
    if(!(a&b))head[a].push_back(b);
33.  
    }
34.  
    }
35.  
    f[0][0]=1;
36.  
    for(int i=1;i<=m 1;i ){
37.  
    for(auto a : state){
38.  
    if(!(g[i]&a)){
39.  
    for(auto b: head[a]){
40.  
    f[i][a] = (f[i][a] f[i-1][b])%mod;
41.  
    }
42.  
    }
43.  
    }
44.  
    }
45.  
    cout<<f[m 1][0];//因为状态表示的是前i行，所以处理到第i 1行
46.  
    return 0;
47.  
    }

3.炮兵阵地

司令部的将军们打算在 N×M 的网格地图上部署他们的炮兵部队。

一个 N×M 的地图由 N 行 M 列组成，地图的每一格可能是山地（用 H 表示），也可能是平原（用 P 表示），如下图。

在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。

图上其它白色网格均攻击不到。

从图上可见炮兵的攻击范围不受地形的影响。

现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

 思路：        

1.  
    
2.  
   #include<iostream>
3.  
   #include<vector>
4.  
    
5.  
   using namespace std;
6.  
   const int maxn = 1e5 10;
7.  
   vector<int>head[1<<11];
8.  
   vector<int>state;
9.  
   int cnt[maxn];
10.  
    int f[2][1<<11][1<<11];
11.  
    int g[110];
12.  
    int check(int x)
13.  
    {
14.  
    return !((x&(x>>1))||(x&(x>>2)));
15.  
    }
16.  
     
17.  
    int count(int x){
18.  
    int res=0;
19.  
    while(x){
20.  
    if(x&1)res ;
21.  
    x>>=1;
22.  
    }
23.  
    return res;
24.  
    }
25.  
    int main(){
26.  
     
27.  
    int n,m;
28.  
    //存图
29.  
    cin>>n>>m;
30.  
    for(int i=1;i<=n;i ){
31.  
    for(int j=0;j<m;j ){
32.  
    char c;
33.  
    cin>>c;
34.  
    if(c=='H')g[i] |= 1<<j;
35.  
    }
36.  
    }
37.  
     
38.  
    //枚举所有合法状态
39.  
    for(int i=0;i<1<<m;i ){
40.  
    if(check(i))
41.  
    {
42.  
    state.push_back(i);cnt[i] = count(i);
43.  
    }
44.  
    }
45.  
     
46.  
    //枚举所有状态能够转移到的状态
47.  
    for(auto a : state){
48.  
    for(auto b : state ){
49.  
    if(!(a&b))head[a].push_back(b);
50.  
    }
51.  
    }
52.  
     
53.  
    for(int i=1;i<=n;i ){
54.  
    for(auto a : state)//第i层的所有状态
55.  
    {
56.  
    if((g[i]&a))continue;
57.  
    for(int b : head[a]){//第i-1
58.  
    for(int c : head[b]){//第i-2层
59.  
    if(!(a&c))//第i层与第i-2层不能互相攻击
60.  
    f[i&1][a][b] = max(f[i&1][a][b],f[i-1&1][b][c] cnt[a]);
61.  
     
62.  
    }
63.  
    }
64.  
    }
65.  
    }
66.  
    int res =0 ;
67.  
    for(auto a:state){
68.  
    for(auto b : state)
69.  
    res = max(res,f[n&1][a][b]);
70.  
    }
71.  
    cout<<res<<endl;
72.  
    return 0;
73.  
    }

4.愤怒的小鸟

5.宝藏

区间dp

1.环形石子

将 n 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。

规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

请编写一个程序，读入堆数 nn 及每堆的石子数，并进行如下计算：

• 选择一种合并石子的方案，使得做 n−1 次合并得分总和最大。
• 选择一种合并石子的方案，使得做 n−1 次合并得分总和最小。

思路：

本题要求每轮合并的石子 必须是相邻的 两堆石子，因此不能采用 Huffman Tree 的模型

这类限制只能合并相邻两堆石子的模型，用到的是经典的 区间DP 模型

考虑如何设定 动态规划 的阶段，既可以表示出初始每个石子的费用，也可以表示出合并后整个堆的费用

不妨把当前合并的石子堆的大小作为DP的阶段

这样 len=1 表示初值，即每个堆只有一个石子； len=n表示终值，即一个堆中有所有的石子

这种阶段设置方法保证了我们每次合并两个区间时，他们的所有子区间的合并费用都已经被计算出来了

阶段设定好后，考虑如何记录当前的状态，无外乎就两个参数：

石子堆的左端点 l
石子堆的右端点 r
 

在考虑一下本题的 环形相邻 情况如何解决，方案有如下两种：

我们可以枚举环中分开的位置，将环还原成链，这样就需要枚举 n 次，时间复杂度为 O(n4)
我们可以把链延长两倍，变成 2n 个堆，其中 i 和 i n 是相同的两个堆，然后直接套 区间DP 模板，但对于 阶段 lenlen 只枚举到 n，根据 状态的定义，最终可以得到所求的方案，时间复杂度为 O(n3)

1.  
   #include<iostream>
2.  
   #include<cstring>
3.  
   using namespace std;
4.  
   const int maxn = 550;
5.  
   int s[maxn];
6.  
   int w[maxn];
7.  
   int f[maxn][maxn];
8.  
   int g[maxn][maxn];
9.  
   int main(){
10.  
    int n;
11.  
    cin>>n;
12.  
    for(int i=1;i<=n;i )cin>>w[i],w[i n] = w[i];
13.  
     
14.  
    for(int i=1;i<=2*n;i ){
15.  
    s[i] = s[i-1] w[i];
16.  
    }
17.  
     
18.  
    memset(f,-0x3f,sizeof f);
19.  
    memset(g,0x3f,sizeof g);
20.  
     
21.  
    for(int len = 1;len<=n;len ){
22.  
    for(int i = 1;i len-1<=2*n;i ){
23.  
    int r = i len-1;
24.  
    if(len==1)g[i][r]=0,f[i][r]=0;
25.  
    else{
26.  
    for(int k=i;k<r;k ){
27.  
    f[i][r] = max(f[i][r],f[i][k] f[k 1][r] s[r]-s[i-1]);
28.  
    g[i][r] = min(g[i][r],g[i][k] g[k 1][r] s[r]-s[i-1]);
29.  
    }
30.  
    }
31.  
    }
32.  
    }
33.  
    int minn = 0x3f3f3f3f,maxx = -0x3f3f3f3f;
34.  
    for(int i=1;i<=n;i ){
35.  
    minn = min(minn,g[i][i n-1]);
36.  
    maxx = max(maxx,f[i][i n-1]);
37.  
    }
38.  
     
39.  
    cout<<minn<<endl;
40.  
    cout<<maxx<<endl;
41.  
    }

3.能量项链

题目：

在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链，在项链上有 N 颗能量珠。

能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。

并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。

因为只有这样，通过吸盘（吸盘是 Mars 人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。

如果前一颗能量珠的头标记为 m，尾标记为 r，后一颗能量珠的头标记为 r，尾标记为 n，则聚合后释放的能量为 m×r×n（Mars 单位），新产生的珠子的头标记为 m，尾标记为 n。

需要时，Mars 人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。

显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

例如：设 N=44，4 颗珠子的头标记与尾标记依次为 (2，3)(3，5)(5，10)(10，2)。

我们用记号 ⊕⊕ 表示两颗珠子的聚合操作，(j⊕k) 表示第 j，k 两颗珠子聚合后所释放的能量。则

第 4、1两颗珠子聚合后释放的能量为：(4⊕1)=10×2×3=60。

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 ((4⊕1)⊕2)⊕3)=10×2×3 10×3×5 10×5×10=710

思路：

 这里的过程同石子合并，这里不难想到若将l到k的珠子合并之后会变成一个首是l而尾k 1的珠子；
 同理若将k 1到r的珠子合并之后会变成一个首是k 1而尾r 1的珠子；

1.  
   #include<iostream>
2.  
   #include<cstring>
3.  
   using namespace std;
4.  
   const int maxn = 210;
5.  
   int w[maxn];
6.  
   int f[maxn][maxn];
7.  
    
8.  
    
9.  
   int main(){
10.  
    int n;
11.  
    cin>>n;
12.  
    for(int i=1;i<=n;i )cin>>w[i],w[i n] = w[i];
13.  
     
14.  
    //memset(f,-0x3f,sizeof f);
15.  
     
16.  
    for(int len =1;len<=n;len ){
17.  
     
18.  
    for(int l=1;l len-1<n*2;l ){
19.  
    int r = l len-1;
20.  
    if(len==1)f[l][r]=0;
21.  
    else
22.  
    for(int k=l;k<r;k ){
23.  
    f[l][r] = max(f[l][r],f[l][k] f[k 1][r] w[l]*w[k 1]*w[r 1]);
24.  
    }
25.  
    }
26.  
    }
27.  
    int res=-0x3f3f3f3f;
28.  
    for(int i=1;i<=n;i )res = max(res,f[i][i n-1]);
29.  
    cout<<res<<endl;
30.  
     
31.  
     
32.  
    return 0;
33.  
    }

4.加分二叉树

设一个 nn 个节点的二叉树 tree 的中序遍历为（1,2,3,…,n1,2,3,…,n），其中数字 1,2,3,…,n1,2,3,…,n 为节点编号。

每个节点都有一个分数（均为正整数），记第 ii 个节点的分数为 didi，tree 及它的每个子树都有一个加分，任一棵子树 subtree（也包含 tree 本身）的加分计算方法如下：     

subtree的左子树的加分 ×× subtree的右子树的加分 ＋＋ subtree的根的分数 

若某个子树为空，规定其加分为 11。

叶子的加分就是叶节点本身的分数，不考虑它的空子树。

试求一棵符合中序遍历为（1,2,3,…,n1,2,3,…,n）且加分最高的二叉树 tree。

要求输出： 

（1）tree的最高加分 

（2）tree的前序遍历

思路：

状态表示：f[i][j] 表示中序遍历是 w[i ~ j] 的所有二叉树的得分的最大值。
状态计算：f[i][j] = max(f[i][k - 1] * f[k 1][j] w[k])，即将f[i][j]表示的二叉树集合按根节点分类，则根节点在 k 时的最大得分即为 f[i][k - 1] * f[k 1][j] w[k]，则f[i][j]即为遍历 k 所取到的最大值。

在计算每个状态的过程中，记录每个区间的最大值所对应的根节点编号。

那么最后就可以通过DFS求出最大加分二叉树的前序遍历了。

1.  
   #include <cstdio>
2.  
   #include <cstring>
3.  
   #include <iostream>
4.  
   #include <algorithm>
5.  
    
6.  
   using namespace std;
7.  
    
8.  
   typedef pair<int, int> PII;
9.  
    
10.  
    const int N = 50;
11.  
     
12.  
    int n;
13.  
    int w[N];
14.  
    unsigned f[N][N];
15.  
    int root[N][N];
16.  
     
17.  
    void dfs(int l, int r)
18.  
    {
19.  
    if (l > r) return;
20.  
     
21.  
    int k = root[l][r];
22.  
    printf("%d ", k);
23.  
    dfs(l, k - 1);
24.  
    dfs(k 1, r);
25.  
    }
26.  
     
27.  
    int main()
28.  
    {
29.  
    scanf("%d", &n);
30.  
    for (int i = 1; i <= n; i ) scanf("%d", &w[i]);
31.  
    for (int len = 1; len <= n; len )
32.  
    for (int l = 1; l len - 1 <= n; l )
33.  
    {
34.  
    int r = l len - 1;
35.  
     
36.  
    for (int k = l; k <= r; k )
37.  
    {
38.  
    int left = k == l ? 1 : f[l][k - 1];
39.  
    int right = k == r ? 1 : f[k 1][r];
40.  
    int score = left * right w[k];
41.  
    if (l == r) score = w[k];
42.  
    if (f[l][r] < score)
43.  
    {
44.  
    f[l][r] = score;
45.  
    root[l][r] = k;
46.  
    }
47.  
    }
48.  
    }
49.  
     
50.  
    printf("%d\n", f[1][n]);
51.  
    dfs(1, n);
52.  
    puts("");
53.  
     
54.  
    return 0;
55.  
    }
56.  
     
57.  
    作者：yxc
58.  
    链接：https://www.acwing.com/solution/content/3804/
59.  
    来源：AcWing
60.  
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

树型dp

1.最长路径

给定一棵树，树中包含 n 个结点（编号1~n）和 n−1 条无向边，每条边都有一个权值。

现在请你找到树中的一条最长路径。

换句话说，要找到一条路径，使得使得路径两端的点的距离最远。

注意：路径中可以只包含一个点。

思路:

 \

1.  
   #include<iostream>
2.  
   #include<cstring>
3.  
   using namespace std;
4.  
   const int maxn = 1e4 10;
5.  
   int h[maxn],e[maxn*2],ne[maxn*2],w[maxn*2],idx;
6.  
    
7.  
   void add(int a,int b,int c){
8.  
   e[idx] = b;
9.  
   ne[idx] = h[a];
10.  
    w[idx] = c;
11.  
    h[a] = idx ;
12.  
    }
13.  
    int res = 0;
14.  
    int dfs(int u,int far){
15.  
    int d1=0,d2=0;
16.  
    int d=0;
17.  
    for(int i=h[u];~i;i=ne[i]){
18.  
    int j = e[i];
19.  
    if(j==far)continue;
20.  
    d = dfs(j,u) w[i];
21.  
    if(d>d1)d2 = d1,d1= d;
22.  
    else if(d>d2)d2=d;
23.  
    }
24.  
    res = max(res,d1 d2);
25.  
    return d1;
26.  
     
27.  
    }
28.  
     
29.  
    int main(){
30.  
    int n;
31.  
    cin>>n;
32.  
    memset(h,-1,sizeof h);
33.  
     
34.  
    for(int i=0;i<n-1;i ){
35.  
    int a,b,c;
36.  
    cin>>a>>b>>c;
37.  
    add(a,b,c);
38.  
    add(b,a,c);
39.  
    }
40.  
    dfs(1,-1);
41.  
    cout<<res<<endl;
42.  
    }

2.树的重心

给定一棵树，树中包含 n 个结点（编号1~n）和 n−1条无向边，每条边都有一个权值。

请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。

思路:其实和上一题差不多,我就复制一个吧

1.  
   #include <cstring>
2.  
   #include <iostream>
3.  
   #include <algorithm>
4.  
    
5.  
   using namespace std;
6.  
    
7.  
   const int N = 10010, M = N * 2, INF = 0x3f3f3f3f;
8.  
    
9.  
   int n;
10.  
    int h[N], e[M], w[M], ne[M], idx;
11.  
    int d1[N], d2[N], p1[N], up[N];
12.  
    bool is_leaf[N];
13.  
     
14.  
    void add(int a, int b, int c)
15.  
    {
16.  
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ;
17.  
    }
18.  
     
19.  
    int dfs_d(int u, int father)//这里是向下递归的过程，目的是得到每个点的向下路径的最大长度和次大长度
20.  
    {
21.  
    d1[u] = d2[u] = -INF;
22.  
    for (int i = h[u]; i != -1; i = ne[i])
23.  
    {
24.  
    int j = e[i];
25.  
    if (j == father) continue;
26.  
    int d = dfs_d(j, u) w[i];
27.  
    if (d >= d1[u])
28.  
    {
29.  
    d2[u] = d1[u], d1[u] = d;
30.  
    p1[u] = j;//表示当前被更新的u这个父节点的下一点为j
31.  
    }
32.  
    else if (d > d2[u]) d2[u] = d;
33.  
    }
34.  
    if (d1[u] == -INF)//如果没有被更新说明是叶节点，那么最大值和次大值都是0，而且标记为叶节点
35.  
    {
36.  
    d1[u] = d2[u] = 0;
37.  
    is_leaf[u] = true;
38.  
    }
39.  
    return d1[u];//每次返回这个最大值
40.  
    }
41.  
     
42.  
    void dfs_u(int u, int father)//第一步向上递归，第二步向下或继续向上递归的过程
43.  
    {
44.  
    for (int i = h[u]; i != -1; i = ne[i])
45.  
    {
46.  
    int j = e[i];
47.  
    if (j == father) continue;//这里不要理解为父节点，其实这句话的根本目的是为了判重，防止回到上一次的
48.  
    //搜索的节点（如果理解为父节点可能比较难解释向上搜索）
49.  
    if (p1[u] == j) up[j] = max(up[u], d2[u]) w[i];
50.  
    //p1[u]==j说明遇到了之前向下递归的那条路径，为了避免路径的重复，
51.  
    //那么便只能用次大值来更新这条路径的长度
52.  
    //up[j] = max(up[u], d2[u]) w[i];这句话是说从j这一节点的向上路径的长度等于它的父节点u继续
53.  
    //向上到其他点的路径或从父节点向下的路径的长度加上u与j直接的距离
54.  
    else up[j] = max(up[u], d1[u]) w[i];
55.  
    dfs_u(j, u);
56.  
    }
57.  
    }
58.  
     
59.  
    int main()
60.  
    {
61.  
    cin >> n;
62.  
    memset(h, -1, sizeof h);
63.  
    for (int i = 0; i < n - 1; i )
64.  
    {
65.  
    int a, b, c;
66.  
    cin >> a >> b >> c;
67.  
    add(a, b, c), add(b, a, c);
68.  
    }
69.  
    dfs_d(1, -1);
70.  
    dfs_u(1, -1);
71.  
    int res = d1[1];
72.  
    for (int i = 2; i <= n; i )
73.  
    if (is_leaf[i]) res = min(res, up[i]);
74.  
    else res = min(res, max(d1[i], up[i]));
75.  
    printf("%d\n", res);
76.  
    return 0;
77.  
    }
78.  
     
79.  
    作者：Accepting
80.  
    链接：https://www.acwing.com/solution/content/13025/
81.  
    来源：AcWing
82.  
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 3.数字转换

如果一个数 x 的约数之和 y（不包括他本身）比他本身小，那么 x 可以变成 y，y 也可以变成 x。

例如，4 可以变为 3，1 可以变为 7。

限定所有数字变换在不超过 n 的正整数范围内进行，求不断进行数字变换且不出现重复数字的最多变换步数。

思路:

纠正:图中6连向3

1.  
   #include <cstring>
2.  
   #include <iostream>
3.  
   #include <algorithm>
4.  
    
5.  
   using namespace std;
6.  
    
7.  
   const int N = 50010, M = N;
8.  
    
9.  
   int n;
10.  
    int h[N], e[M], w[M], ne[M], idx;
11.  
    int sum[N];
12.  
    bool st[N];
13.  
    int ans;
14.  
     
15.  
    void add(int a, int b)
16.  
    {
17.  
    e[idx] = b, ne[idx] = h[a], h[a] = idx ;
18.  
    }
19.  
     
20.  
    int dfs(int u)
21.  
    {
22.  
    st[u] = true;
23.  
     
24.  
    int dist = 0;
25.  
    int d1 = 0, d2 = 0;
26.  
    for (int i = h[u]; ~i; i = ne[i])
27.  
    {
28.  
    int j = e[i];
29.  
    if (!st[j])
30.  
    {
31.  
    int d = dfs(j);
32.  
    dist = max(dist, d);
33.  
    if (d >= d1) d2 = d1, d1 = d;
34.  
    else if (d > d2) d2 = d;
35.  
    }
36.  
    }
37.  
     
38.  
    ans = max(ans, d1 d2);
39.  
     
40.  
    return dist 1;
41.  
    }
42.  
     
43.  
    int main()
44.  
    {
45.  
    cin >> n;
46.  
    memset(h, -1, sizeof h);
47.  
     
48.  
    for (int i = 1; i <= n; i )
49.  
    for (int j = 2; j <= n / i; j )
50.  
    sum[i * j] = i;
51.  
     
52.  
    for (int i = 2; i <= n; i )
53.  
    if (sum[i] < i)
54.  
    add(sum[i], i);
55.  
     
56.  
    for (int i = 1; i <= n; i )
57.  
    if (!st[i])
58.  
    dfs(i);
59.  
     
60.  
    cout << ans << endl;
61.  
     
62.  
    return 0;
63.  
    }

4.二叉苹果树

有一棵二叉苹果树，如果树枝有分叉，一定是分两叉，即没有只有一个儿子的节点。

这棵树共 N 个节点，编号为 1 至 N，树根编号一定为 1。

我们用一根树枝两端连接的节点编号描述一根树枝的位置。

一棵苹果树的树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。

这里的保留是指最终与1号点连通。

题意:

给定一棵含有 n 个结点的树，树根编号为 1，且树上的每条边有一个边权 w
要求我们只保留树中的 m 条边，使得 树根 所在的 连通块 的所有边 边权之和 最大

思路:

这题的题面其实就是 有依赖的背包 模型，不同的是把 物品价值 分给了 边 而不是 点

不过，对于一棵树来说，任意节点的入边（连向父节点的边） 都是 唯一 的

所以 边权 和 点权 在确定树的 根节点 以后，是可以视作一个东西的（入边价值 视作 该点价值）

1.  
   #include <iostream>
2.  
   #include <cstring>
3.  
    
4.  
   using namespace std;
5.  
    
6.  
   const int N = 110, M = N << 1;
7.  
    
8.  
   int n, m;
9.  
   int h[N], e[M], w[M], ne[M], idx;
10.  
    int f[N][N];
11.  
     
12.  
    void add(int a, int b, int c)
13.  
    {
14.  
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ;
15.  
    }
16.  
    void dfs(int u, int father)
17.  
    {
18.  
    for (int i = h[u]; ~i; i = ne[i])
19.  
    {
20.  
    int ver = e[i];
21.  
    if (ver == father) continue;
22.  
    dfs(ver, u);
23.  
    for (int j = m; j >= 0; j -- )
24.  
    for (int k = 0; k <= j - 1; k ) //枚举体积预留一条连向父节点的边
25.  
    f[u][j] = max(f[u][j], f[u][j - k - 1] f[ver][k] w[i]);
26.  
    }
27.  
    }
28.  
    int main()
29.  
    {
30.  
    memset(h, -1, sizeof h);
31.  
    scanf("%d%d", &n, &m);
32.  
    for (int i = 1; i < n; i )
33.  
    {
34.  
    int a, b, c;
35.  
    scanf("%d%d%d", &a, &b, &c);
36.  
    add(a, b, c), add(b, a, c);
37.  
    }
38.  
    dfs(1, -1);
39.  
    printf("%d\n", f[1][m]);
40.  
    return 0;
41.  
    }
42.  
     
43.  
    作者：彩色铅笔
44.  
    链接：https://www.acwing.com/solution/content/65600/
45.  
    来源：AcWing
46.  
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

5.战略游戏【树形DP 状态机模型】

给定一棵包含 n 个结点的 树，以及 树 上的 n−1 条边

我们需要在这 n 个结点中，选择一定数量的结点放上 哨兵

最终要求，树中任意n−1 条边的左右两端，至少有一个结点上放置了 哨兵

求解一个 方案，该方案满足上述要求，且放置的哨兵数量 最少，输出该 方案 放置的 哨兵数量

思路:

显然我们不能 暴力枚举 树中所有结点 选(1) 与 不选(0) 的状态（时间复杂度 为 O(2n)

因此，会想到采用 分治 思想：
考虑以结点 u 为 根节点 的子树，该子树所有的 方案，可以由当前结点 放 或 不放哨兵 进行划分

这也是一种 状态机模型，我简略的绘制一下这个状态机：

1.  
   #include <iostream>
2.  
   #include <cstring>
3.  
   #include <algorithm>
4.  
    
5.  
   using namespace std;
6.  
    
7.  
   const int N = 1510;
8.  
    
9.  
   int n;
10.  
    int h[N], e[N], ne[N], idx;
11.  
    int f[N][2];
12.  
    bool not_root[N];
13.  
     
14.  
    void add(int a, int b)
15.  
    {
16.  
    e[idx] = b, ne[idx] = h[a], h[a] = idx ;
17.  
    }
18.  
    void dfs(int u)
19.  
    {
20.  
    f[u][0] = 0, f[u][1] = 1; //initialize
21.  
    for (int i = h[u]; ~i; i = ne[i])
22.  
    {
23.  
    int j = e[i];
24.  
    dfs(j);
25.  
    f[u][0] = f[j][1];
26.  
    f[u][1] = min(f[j][0], f[j][1]);
27.  
    }
28.  
    }
29.  
    int main()
30.  
    {
31.  
    while (~scanf("%d", &n))
32.  
    {
33.  
    memset(h, -1, sizeof h); idx = 0;
34.  
    memset(not_root, 0, sizeof not_root);
35.  
    for (int i = 0; i < n; i )
36.  
    {
37.  
    int a, b, siz;
38.  
    scanf("%d:(%d) ", &a, &siz);
39.  
    while (siz -- )
40.  
    {
41.  
    scanf("%d", &b);
42.  
    add(a, b);
43.  
    not_root[b] = true;
44.  
    }
45.  
    }
46.  
    int root = 0;
47.  
    while (not_root[root]) root ;
48.  
    dfs(root);
49.  
    printf("%d\n", min(f[root][0], f[root][1]));
50.  
    }
51.  
    return 0;
52.  
    }
53.  
     
54.  
    作者：彩色铅笔
55.  
    链接：https://www.acwing.com/solution/content/66365/
56.  
    来源：AcWing
57.  
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

6皇宫看守

太平王世子事件后，陆小凤成了皇上特聘的御前一品护卫。

皇宫各个宫殿的分布，呈一棵树的形状，宫殿可视为树中结点，两个宫殿之间如果存在道路直接相连，则该道路视为树中的一条边。

已知，在一个宫殿坐镇的守卫不仅能够观察到本宫殿的状况，还能观察到与该宫殿直接存在道路相连的其他宫殿的状况。

大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。

可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留在这的护卫。

帮助陆小凤布置护卫，在看守全部宫殿的前提下，使得花费的经费最少。

思路:

在 战略游戏 中，题目要求的放置方案是 每条边 都被 观察 到，而本题则是要求 每个点 都被 观察 到

因此我们还是同样使用 树形DP 来求解方案

本题的要求相对于 战略游戏 ，稍稍增加了一些 难度，原因如下：

如果只是要求 每条边 被 观察 到，那么我们在处理 父节点 时，枚举到一个 子节点 就可以直接进行讨论

父节点 放置 哨兵，所有子节点都 可放可不放 哨兵
父节点 不放 哨兵，所有子节点 都要放置 哨兵
但是在本题的 要求 中，每条边 变成了 每个点 就会出现如下三种情况：

父节点 放置 哨兵，所有子节点都 可放可不放 哨兵
父节点 不放 哨兵，但是他至少有一个 子节点 放置哨兵，观察住了他
父节点 不放 哨兵，但 父节点 的 父节点 放置哨兵观察，则 子节点 可放可不放 哨兵
这样每个结点就有 三种情况 要转移，简略状态机模型如下：

被父节点观察 （0）
被子节点观察 （1）
被自己来观察 （2）

        

1.  
   #include <iostream>
2.  
   #include <cstring>
3.  
   using namespace std;
4.  
    
5.  
   /*
6.  
   以下注释为早期笔记，希望对你有所帮助
7.  
    
8.  
   状态机 树形Dp问题
9.  
   状态表示:
10.  
    f(i, 0)：第i号结点被他的父结点安排的守卫看住的方案数
11.  
    f(i, 1)：第i号结点被他的子结点安排的守卫看住的方案数
12.  
    f(i, 2)：第i号结点自己安排守卫看住的方案数
13.  
    状态计算:(j是i的子结点)
14.  
    f(i, 0) = sum{min(f(j,1), f(j,2))}
15.  
    i是被他父结点看住的，那他的子结点要么自己看自己，要么被自己的子结点看住
16.  
    f(i, 1) = min{w(k) f(k, 2) - sum{min(f(j,1), f(j,2))}}
17.  
    i如果是被子结点看住的，那么就要枚举他是被哪个子结点看住的所有方案，对所有方案求最小值
18.  
    这里的sum不包括j==k的情况，因此需要手动额外减去
19.  
    f(i, 2) = sum{min(f(j,0), f(j,1), f(j,2))} w(u)
20.  
    i是被自己看住的，那他的子结点可以被父结点看住，可以自己看自己，也可以被自己的子结点看住
21.  
    */
22.  
    const int N = 1510;
23.  
    int n;
24.  
    int h[N], w[N], e[N], ne[N], idx;
25.  
    int f[N][3];
26.  
    bool st[N];
27.  
     
28.  
    void add(int a, int b) {
29.  
    e[idx] = b, ne[idx] = h[a], h[a] = idx ;
30.  
    }
31.  
    void dfs(int u) {
32.  
    f[u][0] = 0;
33.  
    f[u][1] = 1e9; //f[u][1]求最小值，初始化为最大值
34.  
    f[u][2] = w[u];//初始化放置自己的代价
35.  
    for (int i = h[u]; ~i; i = ne[i]) {
36.  
    int j = e[i];
37.  
    dfs(j);
38.  
    f[u][0] = min(f[j][1], f[j][2]);
39.  
    f[u][2] = min(min(f[j][0], f[j][1]), f[j][2]);
40.  
    }
41.  
    for (int i = h[u]; ~i; i = ne[i]) {
42.  
    int j = e[i];
43.  
    //f[u][0]中记录了sum{min(f(j,1), f(j,2))}，再从中减去对应的贡献即可得到remain ver
44.  
    f[u][1] = min(f[u][1], f[u][0] f[j][2] - min(f[j][1], f[j][2]));
45.  
    }
46.  
    }
47.  
    int main() {
48.  
    memset(h, -1, sizeof h);
49.  
    cin >> n;
50.  
    for (int i = 1; i <= n; i) {
51.  
    int id, cnt, cost;
52.  
    cin >> id >> cost >> cnt;
53.  
    w[id] = cost;
54.  
    while (cnt--) {
55.  
    int ver;
56.  
    cin >> ver;
57.  
    add(id, ver);
58.  
    st[ver] = true;
59.  
    }
60.  
    }
61.  
    int root = 1;
62.  
    while (st[root]) root;
63.  
    dfs(root);
64.  
    printf("%d\n", min(f[root][1], f[root][2]));
65.  
    return 0;
66.  
    }
67.  
     
68.  
    作者：彩色铅笔
69.  
    链接：https://www.acwing.com/solution/content/66594/
70.  
    来源：AcWing
71.  
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这篇好文章是转载于：学新通技术网