蓝桥杯冲刺 - Lastweek - 你离省一仅剩一步之遥！！！(掌握【DP】冲刺国赛)

💬前言

💡本文以经典DP入手，带你走进DP的大门，感受DP的魅力
🔥🔥🔥DP是 $重中之重$ ，它能决定你的最终名次
📌在比赛中DP是难点也是重点，最重要的是它的分值比重大
📌DP虽难但也有规律可循，有大量的例题模板，经典DP，考题往往会在基本理论的基础上进行变化
📌考场上要能准确看出是哪种类型的DP，就能快速入手尝试突破。
🏁🏁 等你掌握DP时就可以自信的和你的对手说：什么档次敢和我写一样的DP题
如果对您有帮助的话还请动动小手 点赞👍，收藏⭐️，关注❤️

🎯week3

🌲day1

0-1背包

01背包问题
给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S。

现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合 S，最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

输入格式
第一行包含整数 k，表示数字集合 S 中数字的个数。

第二行包含 k 个整数，其中第 i 个整数表示数字集合 S 中的第 i 个数 si。

第三行包含整数 n。

第四行包含 n 个整数，其中第 i 个整数表示第 i 堆石子的数量 hi。

输出格式
如果先手方必胜，则输出 Yes。

否则，输出 No。

数据范围
1≤n,k≤100,
1≤si,hi≤10000
输入样例：
2
2 5
3
2 4 7
输出样例：
Yes

---

背包串联：多重背包 拆分为 0-1背包

扩：谈钱购买时，消耗的体积就是物品的价值:v = w (还有其他变式)

---

2023-DP-先会朴素

#include <bits/stdc++.h>using namespace std;const int N = 1010;int f[N][N];
int n,m;
int v,w;int main()
{scanf("%d%d",&n,&m);for(int i = 1; i <= n; i++){scanf("%d%d", &v, &w);for(int j = 0; j <= m; j++)if(j >= v)f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w); //可放 可不放else f[i][j] = f[i - 1][j]; //放不下当前物品-只能不放}printf("%d", f[n][m]);return 0;
}

(优化原理 - 等式错位相减)

#include <iostream>
#include<cstdio>//scanf && printf
#include<algorithm>//maxusing namespace std;const int N = 1010;
int n,m;
int v,w;//可边输入边判断, 也可以存下每种物品的体积v[i]和价值w[i]
int f[N];//f[j] ：体积为j时的最大价值
int main()
{scanf("%d%d", &n, &m);for(int i = 0; i < n; i++){scanf("%d%d",&v, &w); //边输入边转移for(int j = m; j >= v; j --)f[j] = max( f[j] , f[j - v] + w);}printf("%d", f[m]);return 0;
}

数组版

#include <iostream>
#include <algorithm>using namespace std;const int N = 1010;int n, m;
int v[N], w[N]; //存物品体积v[N],价值w[N]
int f[N];int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++ ) scanf("%d%d", &v[i], w[i]);for (int i = 1; i <= n; i ++ )for (int j = m; j >= v[i]; j -- )f[j] = max(f[j], f[j - v[i]] + w[i]);printf("%d", f[m]);return 0;
}

完全背包

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

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

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

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

10

二维朴素

const int N = 1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main()
{cin >> n >> m;for(int i = 1;i <= n;i++)scanf("%d%d",&v[i],&w[i]);for(int i = 1;i <= n;i++)for(int j = 0;j <= m;j++) //体积为j时选择放入的物品{f[i][j] = f[i-1][j]; //不能放时保存上一个值if(j >= v[i]) f[i][j] = max(f[i][j] , f[i][j - v[i]] + w[i]);  //能放时，比较最优解}cout << f[n][m] << endl;return 0;
}

---

一维优化：

#include<iostream>
#include<algorithm>using namespace std;const int N = 1010;int n, m;
int f[N];int main()
{scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) {int v, w;scanf("%d%d", &v, &w);for(int j = v; j <= m; j++)f[j] = max(f[j], f[j - v] + w);}printf("%d", f[m]);return 0;
}

开数组先读入，再枚举计算

#include<isotream>using namespace std;const int N = 1010;
int n,m;
int v[N],w[N],f[N];int main()
{cin >> n >> m; //n种物品，容量m的背包for(int i = 1; i <= n; i++)scanf("%d%d", &v[i], &w[i]);for(int i = 1; i <= n; i++)for(int j = v[i]; j <= m; j++) //体积为j时选择放入的物品f[j] = max(f[j] , f[j - v[i]] + w[i]);     //【好记：与01背包不同按从小到大枚举体积：得max_w】cout << f[m] << endl;return 0;
}

多重背包

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

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

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

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤100
0<vi,wi,si≤100
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10

一、状态表示：f[i][j]
1. 集合：从前i个物品中选,且总体积不超过j的所有方案的集合.
2. 属性：最大值二、状态计算：
1. 思想-----集合的划分
2. 集合划分依据：根据第i个物品有多少个来划分.含0个、含1个···含k个.
状态表示与完全背包朴素代码一样均为：
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);时间复杂度O(n∗v∗s)

最精简版-边读入边计算【思想：拆成0-1背包判断】

#include <iostream>using namespace std;const int N = 1010;int f[N];
int n, m;
int v, w, s;int main()
{scanf("%d%d", &n, &m);while(n--)//n之后没用,可以n-- , 也可for(int i = 1; i <= n; i++){scanf("%d%d%d", &v, &w, &s);for(int i = 1;i <= s; i++)//拆成s件相同价值的物品 --> s次0-1背包计算for(int j = m; j >= v ; j--)f[j] = max(f[j], f[j - v] + w);}printf("%d", f[m]);
}

朴素版

#include <iostream>
#include <algorithm>using namespace std;
const int N = 110;int v[N], w[N], s[N];
int f[N][N];
int n, m;int main(){cin >> n >> m;for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i] >> s[i];for(int i = 1; i <= n; i ++){//枚举种类for(int j = 1; j <= m; j ++){//枚举体积for(int k = 0; k <= s[i]; k ++){//枚举件数if(j >=  k * v[i]){//转移限制条件f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);//取k件物品减对应k件物品价值}}}}cout << f[n][m] << endl;return 0;
}

多重背包 II

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

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

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

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000
提示：
本题考查多重背包的二进制优化方法。

输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10

---

二进制优化 + 0-1背包模板
思想举例：
7 的二进制111 ：3位选不选0/1
1 2 4可组合成 0-7

但取 s = 10 ，非2^n - 1  
就用 s - 1 - 2 - 4  = 3  < 8 ,已拆分的1 2 4对应二进制：1 10 100  【剩下的3单独加入集合】1 2 4 3 -- >枚举  (全不选) 0 - 10 (全选)   优化完能解决: 枚举v[i]物品体积 * s[i]每种物品个数 * m体积限制  ：  4e10   

不开数组版-边读入边计算[模板]

a, b, s : 每种物品: 体积v 价值w 数量s

#include<iostream>
#include<cstdio>using namespace std;const int N = 12010, M = 2010;//N:拆分后物品件数最多12000 , M : 背包体积int n, m;
int v[N], w[N]; //逐一枚举最大是N*logS  
int f[M]; // 背包体积 < M , f[j]: 体积为j时的最大价值int main()
{scanf("%d%d", &n, &m); //n件种类组合，m总体积int cnt = 0; //记录拆分后种类 ,最后 n  = cntfor(int i = 1; i <= n; i++){int a, b, s;//【开局部变量的好处就是可以在不同作用域内有多个重名但不冲突】 scanf("%d%d%d", &a, &b, &s);  //不能用v,w和数组重名！！！ int k = 1; //(乘积用1)：拆分初始项1  ，k *= 2    1 2 4 （1 10 100）...while(k <= s){cnt ++;v[cnt] = a * k;   // 原来共 a * s  拆成 a * 1 + a * 2 + a * 4 ....  w[cnt] = b * k;s -= k;k *= 2;  //也可以 k <<= 1}if(s > 0)// 最后若非 2^n-1  , 取 s 与 (2^n-1) 的余数   ，如 10  ，1 2 4 ... 3  ,则最后一项取 3v,3w{cnt ++;v[cnt] = a * s;   w[cnt] = b * s;}}n = cnt;  //*每个拆分的背包占体积不同 -- 种类不同（变多） //拆项后转化成01背包一维优化for(int i = 1; i <= n ; i ++)for(int j = m ; j >= v[i]; j --)f[j] = max(f[j], f[j - v[i]] + w[i]);printf("%d", f[m]);return 0;
}

开数组版-存每种物品属性

a[N], b[N], s[N];每种物品: 体积v 价值w 数量s

#include<iostream>using namespace std;const int N = 12010, M = 2010;//N:拆分后物品件数最多12000 , M : 背包体积int n, m;
int v[N], w[N]; //逐一枚举最大是N*logS  
int f[M]; // 背包体积 < M , f[j]: 体积为j时的最大价值
int a[N], b[N], s[N];//每种物品: 体积v 价值w 数量sint main()
{scanf("%d%d", &n, &m); //n件种类组合，m总体积int cnt = 0; //记录拆分后种类 ,最后 n  = cntfor(int i = 1;i <= n;i++) scanf("%d%d%d", &a[i], &b[i], &s[i]);  //不能用v,w和数组重名！！！for(int i = 1;i <= n;i++){int k = 1; //(乘积用1)：拆分初始项1  ，k *= 2    1 2 4 （1 10 100）...while(k <= s[i]){cnt ++ ;v[cnt] = a[i] * k;   // 原来共 a * s  拆成 a * 1 + a * 2 + a * 4 ....  w[cnt] = b[i] * k;s[i] -= k;k *= 2;  //也可以 k <<= 1}if(s[i] > 0)// 最后若非 2^n-1  , 取 s 与 (2^n-1) 的余数   ，如 10  ，1 2 4 ... 3  ,则最后一项取 3v,3w{cnt ++ ;v[cnt] = a[i] * s[i];   w[cnt] = b[i] * s[i];}}n = cnt;  //*每个拆分的背包占体积不同 -- 种类不同（变多） //拆项后转化成01背包一维优化for(int i = 1;i <= n ;i ++)for(int j = m ;j >= v[i];j --)f[j] = max(f[j],f[j-v[i]] + w[i]);printf("%d", f[m]);return 0;
}

分组背包

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

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。

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

输出最大价值。

输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。

接下来有 N 组数据：

每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤100
0<Si≤100
0<vij,wij≤100
输入样例

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

输出样例：

8

f[j]:只从前i组物品中选, 且总体积不超过j的选法
不选:f[j] , 选：f[j - v[i][k]] + w[i][k] ： 比较取max继续转移下一个状态

#include <iostream>
#include <algorithm>using namespace std;const int N = 110;int n, m;
int v[N][N], w[N][N], s[N];  //二维存入物品体积、价值 ：v[i][k] (第i组第k件物品体积)
int f[N];  //f[j] : 只从前i组物品中选, 且总体积不超过j的选法int main()
{scanf("%d%d", &n, &m);//依题读入for (int i = 0; i < n; i ++ ){scanf("%d", &s[i]);//存每组物品数量for (int j = 0; j < s[i]; j ++ )//读入每组物品：下标从0开始scanf("%d%d", &v[i][j], &w[i][j]);}for (int i = 0; i < n; i ++ )for (int j = m; j >= 0; j -- )  //0-1背包模板 【注意写法：k在下面枚举,此时下标还无法表示:只能写j >= 0(且j与k枚举顺序不能变)】for (int k = 0; k < s[i]; k ++ )  //每组物品下标从0开始if (v[i][k] <= j)  //条件限制：能放的下此物品 v[i][k] : 第i组的第k件物品f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);   //选或不选printf("%d", f[m]);return 0;
}

🌲day2

数字三角形 - 线性DP

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

	        73   88   1   02   7   4   44   5   2   6   5

输入格式
第一行包含整数 n，表示数字三角形的层数。

接下来 n 行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。

输出格式
输出一个整数，表示最大的路径数字和。

数据范围
1≤n≤500,
−10000≤三角形中的整数≤10000
输入样例：

5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

输出样例：

30

思路：
路径从起点走到终点的距离 == 终点走回起点的距离
逆序从最后一行开始走a[n][i] -->a[1][1] ,只需要一维：最终max都转移到f[1] : 以第n行第i列走到[1,1]的最大值max
往上转移：转移到上层[i][j] , 则下层相对于上层的下标为[i + 1][j], [i + 1][j + 1]
i用循环等效对应, f[j]一维枚举计算[j]与[j+1]：最后一轮i = 1,最终 f[1] 存转移到 a[1][1] 的max

朴素版

#include <iostream>
#include <algorithm>using namespace std;const int N = 510, INF = 1e9;int n;
int a[N][N];//存三角形
int f[N][N];//f[n][i] : 到第n个点的路径之和maxint main()
{scanf("%d", &n);for (int i = 1; i <= n; i ++ ) //dp用到下标i - 1 ： 从1开始for (int j = 1; j <= i; j ++ )scanf("%d", &a[i][j]);//i = 1更准确, 0当然也可以（初始-INF需包括三角形及其边界）for (int i = 1; i <= n; i ++ )//下三角形  //【 因为题目n∈[-1e4,1e4], 存在负数 】, 所以应该将两边也设为-INFfor (int j = 0; j <= i + 1; j ++ )f[i][j] = -INF;//求最大边界不影响 取负无穷：-INFf[1][1] = a[1][1];//下标不越界：初始起点需赋值for (int i = 2; i <= n; i ++ )//2开始for (int j = 1; j <= i; j ++ )f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];//选取上一个状态大的 + 此状态值//等效f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);int res = -INF;//求最大, 初始负无穷：-INFfor (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]); //最后一行都是最终状态：选取maxprintf("%d\n", res);return 0;
}

从下往上优化：

#include<iostream>
#include<cstdio>
#include<algorithm>using namespace std;const int N = 1010;int f[N];
int a[N][N];int main()
{int n;scanf("%d", &n);for(int i = 1; i <= n; i++)//读入三角形, 为了不判断边界:从1开始for(int j = 1; j <= i; j++)scanf("%d", &a[i][j]);for(int i = n; i >= 1; i--) //推导后的一维优化：i=n 逆序从最后一行开始, j正序 ： 从最后一行走到顶【顶只有1个】for(int j = 1; j <= i; j++)f[j] = max(f[j], f[j + 1]) + a[i][j];//往上走：转移下标为j和j + 1printf("%d", f[1]);return 0;
}

1015. 摘花生 - 数字三角形

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

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

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

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

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

输入格式
第一行是一个整数T，代表一共有多少组数据。
接下来是T组数据。
每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。
每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。
输出格式
对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。
数据范围

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

输入样例：

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

输出样例：

8
16

#include <iostream> 
#include <algorithm> //需记库 
using namespace std;const int N = 105;int n,m;
int w[N][N],f[N][N];int main(){int T;scanf("%d",&T);while(T--){scanf("%d%d",&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];printf("%d\n",f[n][m]);}return 0;
} 

🌲day3

最长上升子序列 - 线性DP

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

输入格式
第一行包含整数 N。

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

输出格式
输出一个整数，表示最大长度。

数据范围
1≤N≤1000，
−$10^9$≤数列中的数≤$10^9$
输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

集合划分：f[i]为以a[i]结尾的最长上升子序列

#include <iostream>
#include <algorithm>using namespace std;const int N = 1010;int n;
int a[N];
int f[N];int main()
{scanf("%d", &n);for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);int res = 0;for (int i = 1; i <= n; i ++ ){f[i] = 1;//以i结尾的子序列：初始长度为本身 = 1for (int j = 1; j < i; j ++ )if (a[i] > a[j])//以i结尾子序列 = 以j结尾的子序列 + 1f[i] = max(f[i], f[j] + 1);res = max(res, f[i]);}printf("%d", res);return 0;
}

1017. 怪盗基德的滑翔翼 - LIS

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

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

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

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

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

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

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

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

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

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

输入格式
输入数据第一行是一个整数K，代表有K组测试数据。

每组测试数据包含两行：第一行是一个整数N，代表有N幢建筑。第二行包含N个不同的整数，每一个对应一幢建筑的高度h，按照建筑的排列顺序给出。

输出格式
对于每一组测试数据，输出一行，包含一个整数，代表怪盗基德最多可以经过的建筑数量。

数据范围
1≤K≤100,
1≤N≤100,
0<h<10000
输入样例：

3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
2 1 3 4 5 6 7 8 9 10

输出样例：

6
6
9

方向确定就只能往一个方向跳（左/右）
如图：起点a[i] ,最长距离就是以a[i] 结尾的最长上升子序列
【图形：先上升再下降（则右边往左看为逆LIS ，左<—右 ,逆序LIS （起点n ，i- -,j- -））

简记：（正向+反向求解LIS ，比较得max）逆序：  起点n ，i--,j-- ，i,j意义与正向一样不变//不用res=0， 正反方向取max for(int i = n; i ;i--) //i > 0{f[i] = 1;for(int j = n;j > i;j --)if(a[i] > a[j])f[i] = max(f[i] , f[j] + 1);  res = max(res,f[i]); //算出一个f[i]就比较一次 }

#include<bits/stdc++.h>#include<algorithm>
using namespace std;const int N = 1010;int n,T;
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]);	//正向求解LISint res = 0;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);  res = max(res,f[i]); //算出一个f[i]就比较一次 }//不用res=0， 正反方向取max for(int i = n; i ;i--) //i > 0{f[i] = 1;for(int j = n;j > i;j --)if(a[i] > a[j])f[i] = max(f[i] , f[j] + 1);  res = max(res,f[i]); //算出一个f[i]就比较一次 }printf("%d\n",res);	}return 0;
}

1014.登山 - LIS

题目描述：

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

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

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

输入格式

第一行包含整数N，表示景点数量。

第二行包含N个整数，表示每个景点的海拔。

输出格式

输出一个整数，表示最多能浏览的景点数。

数据范围

2≤N≤1000

输入样例：

8
186 186 150 200 160 130 197 220

输出样例：

4

按编号递增顺序浏览 --> 必须是子序列
先严格上升再严格下降
一旦开始下降就不能上升了
分类：以a[k]为极值点（转折）的子序列的max（正+反-1：有一个共同重叠点）

简记： a[k]的max：上升存f[i],下降存g[i] ，res = max(res  , f[i] + g[i] - 1)

#include<bits/stdc++.h>#include<algorithm>
using namespace std;const int N = 110;int n,T;
int a[N];
int g[N],f[N];
int main()
{scanf("%d",&n);for(int i = 1;i <= n;i++) scanf("%d",&a[i]);	//正向求解LIS存到f[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);  }//反向求解LIS 存到g[i] for(int i = n;i;i--){g[i] = 1;for(int j = n;j > i;j--)if(a[i] > a[j])g[i] = max(g[i], g[j] + 1);} int res = 0;for(int i = 1;i <= n;i++) res = max(res , f[i] + g[i] - 1);printf("%d\n",res);	return 0;
}

最长公共子序列 - 线性DP

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

输入格式
第一行包含两个整数 N 和 M。

第二行包含一个长度为 N 的字符串，表示字符串 A。

第三行包含一个长度为 M 的字符串，表示字符串 B。

字符串均由小写字母构成。

输出格式
输出一个整数，表示最大长度。

数据范围
1≤N,M≤1000
输入样例：

4 5
acbd
abedc

输出样例：

3

---

---

#include <iostream>
#include <algorithm>using namespace std;const int N = 1010;int n, m;
char a[N], b[N];
int f[N][N];int main()
{scanf("%d%d", &n, &m);scanf("%s%s", a + 1, b + 1);//转移方程用到下标1,从1开始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]);//不相等有一个指针向前移动,i或j, 选取转移后的maxif (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);//两个字符相等,双指针继续判断下一位//else f[i][j] = max(f[i - 1][j] , f[i][j - 1]); //按逻辑写这里 }printf("%d\n", f[n][m]);return 0;
}

🌲day4

最短编辑距离 - 线性DP

给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：

删除–将字符串 A 中的某个字符删除。
插入–在字符串 A 的某个位置插入某个字符。
替换–将字符串 A 中的某个字符替换为另一个字符。
现在请你求出，将 A 变为 B 至少需要进行多少次操作。

输入格式
第一行包含整数 n，表示字符串 A 的长度。

第二行包含一个长度为 n 的字符串 A。

第三行包含整数 m，表示字符串 B 的长度。

第四行包含一个长度为 m 的字符串 B。

字符串中均只包含大小写字母。

输出格式
输出一个整数，表示最少操作次数。

数据范围
1≤n,m≤1000
输入样例：

10 
AGTCTGACGC
11 
AGTAAGTAGGC

输出样例：

4

---

题意: 每次操作可改变一个元素[增 删 改], 求使得a[]与b[]相等的最少操作次数
集合表示 ：f[i][j] : $a_1......a_i与b_1......b_j相等匹配$
状态划分 ： 增 删 改
增：$a[i]与b[j]中,a的前i个与b的前j-1个匹配，a需增添一个与b[j]相等的元素,对应f[i-1][j]+1$
删：$a[i]与b[j]中,a的前i-1个与b的前j个匹配，需删除a[i], 对应f[i][j - 1] + 1 $
改:【分两种情况 加0 或 加1】
~ ① $a[i]与b[j]中,a的前i-1个与b的前j-1个匹配，需修改a[i],使得a[i]==b[j],对应f[i-1][j-1]+1$
~ ② $a[i]与b[j]中,a的前i-1个与b的前j-1个匹配，且a[i]==b[j]则无需操作,对应f[i-1][j-1]+0$
边界:$f[0][i]：a增加i次变成b,f[i][0]：a删除i次变成b$

#include <iostream>
#include <algorithm>using namespace std;const int N = 1010;int n, m; //strlen(a), strlen(b)
char a[N], b[N];
int f[N][N];int main()
{scanf("%d%s", &n, a + 1); //【转移方程涉及 i - 1为了省去边界判断, 最好初始化从1开始】scanf("%d%s", &m, b + 1); //[否则影响如求min碰到边界0则被边界更新为0,出错]//边界for (int i = 0; i <= m; i ++ ) f[0][i] = i; //a前0个字符与b的前i个字符匹配：需要添加i次for (int i = 0; i <= n; i ++ ) f[i][0] = i; //a前i个字符与b的前0个字符匹配：需要删除i次for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ ){f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1); //增, 删//if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]); //else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1); f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]) ); //改的两种情况简写：+(表达式返回值)}printf("%d\n", f[n][m]); //把a的前n个字母变成b的前m个字母return 0;
}

编辑距离 - 线性DP

给定 n 个长度不超过 10 的字符串以及 m 次询问，每次询问给出一个字符串和一个操作次数上限。

对于每次询问，请你求出给定的 n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。

每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

输入格式
第一行包含两个整数 n 和 m。

接下来 n 行，每行包含一个字符串，表示给定的字符串。

再接下来 m 行，每行包含一个字符串和一个整数，表示一次询问。

字符串中只包含小写字母，且长度均不超过 10。

输出格式
输出共 m 行，每行输出一个整数作为结果，表示一次询问中满足条件的字符串个数。

数据范围
1≤n,m≤1000,

输入样例：

3 2
abc
acd
bcd
ab 1
acbd 2

输出样例：

1
3

多次求最短编辑距离【封装】
思路： 求出最短编辑距离 判断 是否不超过上限limit :
$if(编辑距离<=limit)res++;$

#include <iostream>
#include <algorithm>
#include <string.h>using namespace std;const int N = 15, M = 1010;int n, m;
int f[N][N];
char str[M][N];int edit_distance(char a[], char b[]) //求a[] 变成 b[] 的最少操作次数 
{int la = strlen(a + 1), lb = strlen(b + 1); //注意首地址从1开始！！！for (int i = 0; i <= lb; i ++ ) f[0][i] = i;for (int i = 0; i <= la; i ++ ) f[i][0] = i;for (int i = 1; i <= la; i ++ )for (int j = 1; j <= lb; j ++ ){f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1); //增, 删f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j])); //改的两种情况-精妙简写}return f[la][lb];
}int main()
{scanf("%d%d", &n, &m);for (int i = 0; i < n; i ++ ) scanf("%s", str[i] + 1); //每行从1开始 存入awhile (m -- ) //每轮询问：【str[][]中有多少个a满足操作次数 <= limit变成b】{char s[N];int limit;scanf("%s%d", s + 1, &limit); //读入b 和 操作次数限制limit  int res = 0;  for (int i = 0; i < n; i ++ )if (edit_distance(str[i], s) <= limit) //【注意传入从0开始！！对应函数内部才为从1开始取长度】res ++ ;printf("%d\n", res);}return 0;
}

🌲day5

石子合并 - 区间DP

设有 N 堆石子排成一排，其编号为 1，2，3，…，N。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

例如有 4 堆石子分别为 1 3 5 2， 我们可以先合并 1、2 堆，代价为 4，得到 4 5 2， 又合并 1，2 堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=24；

如果第二步是先合并 2，3 堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22。

问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

输入格式
第一行一个数 N 表示石子的堆数 N。

第二行 N 个数，表示每堆石子的质量(均不超过 1000)。

输出格式
输出一个整数，表示最小代价。

数据范围
1≤N≤300
输入样例：

4
1 3 5 2

输出样例：

22

限制：每次只能合并相邻的两堆 ==> 根据限制划分：
第k堆为最后一次合并: $f[l][k]+f[k+1][r]+s[r]-s[l-1];$(区间和：代价用前缀和计算)

---

#include <iostream>
#include <algorithm>using namespace std;const int N = 310;int n;
int s[N];
int f[N][N];int main()
{scanf("%d", &n);for (int i = 1; i <= n; i ++ )//读入 , 初始化前缀和{scanf("%d", &s[i]);s[i] += s[i - 1];}//【区间枚举】for (int len = 2; len <= n; len ++ )//枚举合并的区间长度 【区间长度是1则不需要代价, 直接从2开始枚举】for (int i = 1; i + len - 1 <= n; i ++ )//枚举起点, 最后一个位置 <= n()不越界{int l = i, r = i + len - 1;f[l][r] = 1e8;//求最小, 初始需超过max边界值 (未初始化则全局为0,算出全为0...)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]);}//先不管最后一次合并的代价, 则代价转移为k点printf("%d\n", f[1][n]);return 0;
}

整数划分 - 计数DP

一个正整数 n 可以表示成若干个正整数之和，形如：$n=n_1+n_2+\dots +n_k$，其中 $n_1\ge n_2\ge \dots \ge n_k,k\ge 1$。

我们将这样的一种表示称为正整数 n 的一种划分。

现在给定一个正整数 n，请你求出 n 共有多少种不同的划分方法。

输入格式
共一行，包含一个整数 n。

输出格式
共一行，包含一个整数，表示总划分数量。

由于答案可能很大，输出结果请对 $10^9+7$ 取模。

数据范围
1≤n≤1000
输入样例:

5

输出样例：

7

y总
佬の思路：
把1,2,3, … n分别看做n个物体的体积,问恰好能装满总体积为n的背包的总方案数 (枚举这n个物体均无数量限制,用完全背包模板)

①完全背包解法
状态表示：
f[i][j]表示只从1~i中选，且总和等于j的方案数

状态转移方程:
f[i][j] = f[i - 1][j] + f[i][j - i];
同完全背包可以一维优化（去掉i）：
f[j] = f[j] + f[j - i]

#include <iostream>
#include <algorithm>using namespace std;const int N = 1010, mod = 1e9 + 7;int n;
int f[N];int main()
{cin >> n;f[0] = 1;for (int i = 1; i <= n; i ++ )for (int j = i; j <= n; j ++ )//从i开始正序f[j] = (f[j] + f[j - i]) % mod;  //【不懂推就记住】可以由上一个状态等价转移cout << f[n] << endl;return 0;
}

②其他算法
状态表示：
f[i][j]表示总和为i，总个数为j的方案数

状态转移方程：
f[i][j] = f[i - 1][j - 1] + f[i - j][j];

#include <iostream>
#include <algorithm>using namespace std;const int N = 1010, mod = 1e9 + 7;int n;
int f[N][N];int main()
{cin >> n;f[1][1] = 1;for (int i = 2; i <= n; i ++ )for (int j = 1; j <= i; j ++ )f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;int res = 0;for (int i = 1; i <= n; i ++ ) res = (res + f[n][i]) % mod;cout << res << endl;return 0;
}

🌲day6

蒙德里安的梦想 - 状压DP

求把 N×M 的棋盘分割成若干个 1×2 的长方形，有多少种方案。

例如当 N=2，M=4 时，共有 5 种方案。当 N=2，M=3 时，共有 3 种方案。

如下图所示：

输入格式
输入包含多组测试用例。

每组测试用例占一行，包含两个整数 N 和 M。

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

输出格式
每个测试用例输出一个结果，每个结果占一行。

数据范围
1≤N,M≤11
输入样例：

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

输出样例：

1
0
1
2
3
5
144
51205

能从k转移到j（即能从前一个状态转移过来）：需满足
① (j & k) == 0 没有冲突：横着放占两格：相邻状态转移不能为同一行
② j | k 不存在连续奇数个0, 剩下的0能够放下竖着的两格才能填满

朴素写法，1000ms

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 12, M = 1 << N;int n, m;
long long f[N][M]; //注意枚举种类很多开LL
bool st[M]; //当前这一列所有的空着的【连续的0是否都为偶数：是否合法】int main() //核心：枚举横着放, 再空位都放竖的(代码枚举横放)
{while (cin >> n >> m, n || m) //n, m都为0停止{for (int i = 0; i < 1 << n; i ++ ) // i < 2^n   枚举所有方案：每行格子选或不选 0或1{int cnt = 0;//统计当前这一段连续0的个数【0为空着的位置】st[i] = true;//假设此方案可行truefor (int j = 0; j < n; j ++ ) //每轮i共选n位(二进制数), 取i的二进制每位判断选或不选 if (i >> j & 1) //i的此位选择1：选择放横的判断i的二进制的j - 1位是否为1{if (cnt & 1) st[i] = false;  //前面有连续的奇数个0, 不能成功转移, 此状态falsecnt = 0; //重新计数}else cnt ++ ; //不选为0  if (cnt & 1) st[i] = false; //最后一段连续个0,若是奇数个0,状态转移失败：【剩下的位置放竖的，必须剩余偶数个0】         }memset(f, 0, sizeof f); //f每轮需要重新置0【多轮输入】f[0][0] = 1; //不可能f[-1][0]转移过来, 空集也代表一种方案【不用填：变相填满】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]) //j为转移后的状态, k为转移前的状态f[i][j] += f[i - 1][k]; //加上之前能转移的方案数cout << f[m][0] << endl; //能转移到m列,且f[m][0]不会"捅"出来, 才是一个合法方案}return 0;
}

去除无效状态的优化写法，230ms

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>using namespace std;typedef long long LL;const int N = 12, M = 1 << N; //枚举所有状态：2^n 【二进制位选或不选】int n, m;
LL f[N][M]; //种类很多 LL
vector<int> state[M]; //存能转移到state[]的状态(存前一个状态) 
bool st[M]; //st预处理无效状态 ： 所有二进制选择方案的状态：是否合法int main()
{while (cin >> n >> m, n || m) //n, m都为0停止{for (int i = 0; i < 1 << n; i ++ ){int cnt = 0; //统计当前方案每一段连续0的个数【0为空着的位置】bool is_valid = true; //此方案是否有效for (int j = 0; j < n; j ++ ) //每轮i共选n位(二进制数), 取i的二进制每位判断选或不选 if (i >> j & 1) //i的二进制的第j - 1位是否为1       i & 1 个位{if (cnt & 1) //连续的0为奇数个{is_valid = false; //方案无效break; }// cnt = 0;  y总写了, 但是my发现这肯定不会执行}else cnt ++ ;if (cnt & 1) is_valid = false;st[i] = is_valid; //st默认初始化为false ：只有is_valid 为true才会标记为合法转移方案}for (int i = 0; i < 1 << n; i ++ )  //减少时间复杂度【预处理所有二进制方案的state状态】{state[i].clear(); //【多轮输入：注意清空】for (int j = 0; j < 1 << n; j ++ )if ((i & j) == 0 && st[i | j]) //符合转移规则state[i].push_back(j); // j为前一个状态能转移到i   }memset(f, 0, sizeof f);f[0][0] = 1;//空集也代表一种方案【不用填：变相填满】for (int i = 1; i <= m; i ++ ) //枚举for (int j = 0; j < 1 << n; j ++ ) //枚举此列所有选与不选状态for (auto k : state[j]) //枚举前一列的二进制排列所有状态【已经预处理状态,累加计算合法状态就行】f[i][j] += f[i - 1][k]; //加上前一个状态i-1的方案数      k = state[j] :表示k转移到jcout << f[m][0] << endl; //能转移到m列,且f[m][0]不会"捅"出来, 才是一个合法方案}return 0;
}

最短Hamilton路径

给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。

Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。

输入格式
第一行输入整数 n。

接下来 n 行每行 n 个整数，其中第 i 行第 j 个整数表示点 i 到 j 的距离（记为 a[i,j]）。

对于任意的 x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]≥a[x,z]。

输出格式
输出一个整数，表示最短 Hamilton 路径的长度。

数据范围
1≤n≤20
0≤a[i,j]≤$10^7$
输入样例：

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例：

18

[最短Hamilton路径] ：等效旅行商问题：不重不漏地经过每个点恰好一次(每个点都有过路费)

状态表示：二进制枚举走或不走
f[i][j] : (二进制表示i的走法)经过i, 倒数第二个点为j的集合

起点和终点固定,中间过程考虑:
1.哪些点被用过
2.目前到哪个点

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 20, M = 1 << N;int n;
int w[N][N];//费用 【邻接矩阵】
int f[M][N];//二进制表示的第i选法 到达第j个点的最小费用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); //求min, 初始化INFf[1][0] = 0; //起点费用0【边界】 for (int i = 0; i < 1 << n; i ++ ) //枚举所有选法for (int j = 0; j < n; j ++ ) //枚举倒数第二个点if (i >> j & 1) 能走到j才有意义！！！【否则剪枝】for (int k = 0; k < n; k ++ ) //过程枚举：起点0-k的最短距离if(i - (1 << j) >> k & 1) //【最后到j，则从起点走到点k的路径不能经过点j】(取0-k中不经过j的状态:减去第j位的1)  f[i][j] = min(f[i][j] , f[i - (1 << j)][k] + w[k][j]); //取0-k中不经过j的状态更新//k视为倒数第二个点 [0 --> k+ k --> j] 费用：f[状态][k] + w[k][j]//'+',-'等算术优先级大于 ">>","<<"等位运算符【不清楚时按逻辑加小括号就行】cout << f[(1 << n) - 1][n - 1]; //最终状态[遍历完所有情况(0~2^n-1)][落到终点]return 0;
}

🌲day7

没有上司的舞会 - 树形DP

给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。

Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。

输入格式
第一行输入整数 n。

接下来 n 行每行 n 个整数，其中第 i 行第 j 个整数表示点 i 到 j 的距离（记为 a[i,j]）。

对于任意的 x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]≥a[x,z]。

输出格式
输出一个整数，表示最短 Hamilton 路径的长度。

数据范围
1≤n≤20
0≤a[i,j]≤$10^7$
输入样例：

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例：

18

---

经典树形DP - 类似状态机+ 邻接矩阵存边
题意

高兴度：不与直接上司匹配 ==> 若选取匹配的两点没有直接连线,加两点的高兴度
==> 即非父子节点【选取没有边相连的两点,加上点(员工)的高兴度】

集合划分 ： 选根 / 不选根
状态：u根(当前) s子节点 转移条件：1表示选, 0表示不选
f[u][0] += max(f[s][1], f[s][1]); **不选根 **： 可以选子节点（选或不选都行）
f[u][1] += f[s][0]; 选根 ：不能选子节点

关键词：最大独立集问题(还没学过)

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 6010;int n;
int h[N], e[N], ne[N], idx;
int happy[N]; //高兴度  ： 可以简写为w[]
int f[N][2];
bool has_fa[N]; //【判断当前节点是否有父节点！（找根,没有父节点则为根）】 (has_father) flagvoid add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
//树形DP
void dfs(int u)
{f[u][1] = happy[u];  //选择当前节点u, 加上自身的高兴度 [过程初始化]for (int i = h[u]; ~i; i = ne[i]) //遍历i的出边 i -> e[i] {int j = e[i]; //对应邻接点 dfs(j); //邻接点先全部初始化,加上自身高兴度//状态机f[u][1] += f[j][0]; f[u][0] += max(f[j][0], f[j][1]);}
}int main()
{scanf("%d", &n);for (int i = 1; i <= n; i ++ ) scanf("%d", &happy[i]); //高兴度 - 类比w[]权值memset(h, -1, sizeof h); //头结点初始化！for (int i = 0; i < n - 1; i ++ ) //读入n-1条有向边{int a, b;scanf("%d%d", &a, &b);add(b, a); has_fa[a] = true; //b -> a : a有父节点b(直接上司)}int root = 1;//找根节点【根节点没有父节点】while (has_fa[root]) root ++ ;  dfs(root); //根节点为起点 ： =>输入起点根root 【状态机dfs-树形DP】 =>返回结果printf("%d\n", max(f[root][0], f[root][1])); //集合划分两种：ans = max(选根的高兴度和, 不选根的高兴度和)return 0;
}