DP

树形DP

285. 没有上司的舞会

Ural 大学有 NN 名职员，编号为 1∼N。
他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。
每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤N。
现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。
在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。
输入格式
第一行一个整数 N。
接下来 N行，第 i 行表示 i 号职员的快乐指数 Hi。
接下来 N−1 行，每行输入一对整数 L,K，表示 K是 L 的直接上司。
输出格式
输出最大的快乐指数。

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <vector>
  6. using namespace std;
  7. const int N = 6010;
  8. int n, w[N];
  9. vector<int> h[N];
  10. bool st[N];
  11. int d[N][2]; // 0 表示选当前节点，1表示不选当前节点的最大值
  13. void dfs(int u) {
  14.     d[u][0] = w[u];
  15.     for (int i = 0; i < h[u].size(); i++) {
  16.         int j = h[u][i];
  17.         dfs(j);
  18.         d[u][0] += d[j][1];
  19.         d[u][1] += max(d[j][0], d[j][1]);
  20.     }
  21. }
  23. int main() {
  24.     cin >> n;
  25.     for (int i = 1; i <= n; i++) {
  26.         cin >> w[i];
  27.     }
  28.     for (int i = 0; i < n - 1; i++) {
  29.         int a, b;
  30.         cin >> a >> b;
  31.         h[b].push_back(a);
  32.         st[a] = true;
  33.     }
  34.     int root;
  35.     for (int i = 1; i <= n; i++) {
  36.         if (!st[i]) {
  37.             root = i;
  38.             break;
  39.         }
  40.     }
  42.     dfs(root);
  43.     cout << max(d[root][1], d[root][0]);
  45. }

3422. 左孩子右兄弟

对于一棵多叉树，我们可以通过 “左孩子右兄弟” 表示法，将其转化成一棵二叉树。
如果我们认为每个结点的子结点是无序的，那么得到的二叉树可能不唯一。
换句话说，每个结点可以选任意子结点作为左孩子，并按任意顺序连接右兄弟。
给定一棵包含 N 个结点的多叉树，结点从 1 至 N 编号，其中 1 号结点是根，每个结点的父结点的编号比自己的编号小。
请你计算其通过 “左孩子右兄弟” 表示法转化成的二叉树，高度最高是多少。
注：只有根结点这一个结点的树高度为 0。
例如如下的多叉树：
image.png
可能有以下 3种 (这里只列出 3 种，并不是全部) 不同的 “左孩子右兄弟”表示：
image.png
其中最后一种高度最高，为 4
输入格式
输入的第一行包含一个整数 N。
以下 N−1 行，每行包含一个整数，依次表示 2 至 N 号结点的父结点编号。
输出格式
输出一个整数表示答案。

  1. //每棵树最大可能形成的高度为其最深子树的高度(根节点高度为0)+其孩子的数量
  2. #include <iostream>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <vector>
  6. const int N = 1e5+10;
  7. using namespace std;
  9. vector<int>h[N];
  10. int dfs(int u){
  11.     int res=0;
  12.     for (int i = 0; i < h[u].size(); i ++ ){
  13.         int j = h[u][i];
  14.         res = max(res,dfs(j));
  15.     }
  16.     res+=h[u].size();
  17.     return res;
  18. }
  20. int main()
  21. {
  22.     int n;
  23.     cin >> n;
  24.     for (int i = 2; i <= n; i ++ ){
  25.         int x;
  26.         cin >> x;
  27.         h[x].push_back(i);
  28.     }
  29.     cout << dfs(1);
  31. }

1220. 生命之树

在X森林里，上帝创建了生命之树。
他给每棵树的每个节点（叶子也称为一个节点）上，都标了一个整数，代表这个点的和谐值。
上帝要在这棵树内选出一个非空节点集 S，使得对于 S 中的任意两个点 a,b，都存在一个点列 {a,v1,v2,…,vk,b} 使得这个点列中的每个点都是 S 里面的元素，且序列中相邻两个点间有一条边相连。
在这个前提下，上帝要使得 S 中的点所对应的整数的和尽量大。
这个最大的和就是上帝给生命之树的评分。
经过 atm 的努力，他已经知道了上帝给每棵树上每个节点上的整数。
但是由于 atm 不擅长计算，他不知道怎样有效的求评分。
他需要你为他写一个程序来计算一棵树的分数。
输入格式
第一行一个整数 n 表示这棵树有 n 个节点。
第二行 n 个整数，依次表示每个节点的评分。
接下来 n−1 行，每行 2 个整数 u,v，表示存在一条 u 到 v 的边。
由于这是一棵树，所以是不存在环的。
树的节点编号从 1 到 n。
输出格式
输出一行一个数，表示上帝给这棵树的分数。
输入样例：
5
1 -2 -3 4 5
4 2
3 1
1 2
2 5
输出样例：
8

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <vector>
  5. using namespace std;
  6. typedef long long LL;
  8. const int N = 1e5+10;
  9. vector<int>e[N];
  10. int w[N];
  11. int n;
  12. LL f[N]; //f[u] 表示以u为根的子树（且包含u）的最大值
  14. // 核心代码，这个是权值在节点上
  15. void dfs(int u,int fa){
  16.     f[u]=w[u];
  17.     for (int i = 0; i < e[u].size(); i ++ ){
  18.         int j = e[u][i];
  19.         if(j==fa){
  20.             continue;
  21.         }
  22.         dfs(j,u);
  23.         f[u] += max(0ll,f[j]);
  24.     }
  25. }
  27. int main()
  28. {
  29.     cin >> n;
  30.     for (int i = 1; i <= n; i ++ ){
  31.         cin >> w[i];
  32.     }
  33.     for (int i = 0; i < n-1; i ++ ){
  34.         int x,y;
  35.         cin >> x >> y;
  36.         e[x].push_back(y);
  37.         e[y].push_back(x);
  38.     }
  39.     dfs(1,-1);
  40.     LL res=f[1];
  41.     for (int i = 2; i <= n; i ++ ){
  42.         res = max(res,f[i]);
  43.     }
  44.     cout << res;
  46. }

1207. 大臣的旅费

很久以前，T王国空前繁荣。
为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。
为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。
同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。
J是T国重要大臣，他巡查于各大城市之间，体察民情。
所以，从一个城市马不停蹄地到另一个城市成了J最常做的事情。
他有一个钱袋，用于存放往来城市间的路费。
聪明的J发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第x千米到第x+1千米这一千米中（x是整数），他花费的路费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。
J大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？
输入格式
输入的第一行包含一个整数 n，表示包括首都在内的T王国的城市数。
城市从 1 开始依次编号，1 号城市为首都。
接下来 n−1 行，描述T国的高速路（T国的高速路一定是 n−1 条）。
每行三个整数 Pi,Qi,Di，表示城市 Pi 和城市 Qi 之间有一条双向高速路，长度为 Di 千米。
输出格式
输出一个整数，表示大臣J最多花费的路费是多少。
输入样例：
5
1 2 2
1 3 1
2 4 5
2 5 4
输出样例：
135

解析：求最长路径即可，即树的直径

image.png

  1. // 两次dfs法，应该是不能处理负权边
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <vector>
  8. using namespace std;
  10. const int N = 100010;
  12. int n;
  13. struct Edge {
  14.     int id, w;
  15. };
  16. vector<Edge> h[N];
  17. int dist[N];
  19. void dfs(int u, int fa) {
  20.     for (int i = 0; i < h[u].size(); i++) {
  21.         int son = h[u][i].id;
  22.         int w = h[u][i].w;
  23.         if (son == fa) {
  24.             continue;
  25.         }
  26.         dist[son] = dist[u] + w;
  27.         dfs(son, u);
  28.     }
  29. }
  31. int main() {
  32.     scanf("%d", &n);
  33.     for (int i = 0; i < n - 1; i++) {
  34.         int a, b, c;
  35.         scanf("%d%d%d", &a, &b, &c);
  36.         h[a].push_back({b, c});
  37.         h[b].push_back({a, c});
  38.     }
  40.     dfs(1, -1);
  42.     int u = 1;
  43.     for (int i = 1; i <= n; i++)
  44.         if (dist[i] > dist[u])
  45.             u = i;
  46.     // 做第二次dfs要清0
  47.     memset(dist, 0, sizeof dist);
  48.     dfs(u, -1);
  50.     for (int i = 1; i <= n; i++)
  51.         if (dist[i] > dist[u])
  52.             u = i;
  54.     int s = dist[u];
  56.     printf("%lld\n", s * 10 + s * (s + 1ll) / 2);
  58.     return 0;
  59. }
  1. // 把一个点挂起来的方法，可以处理负权边
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <vector>
  8. using namespace std;
  10. const int N = 100010;
  12. int n;
  13. struct Edge {
  14.     int id, w;
  15. };
  16. vector<Edge> h[N];
  17. int dist[N][2]; // 以i为根节点的最大值和次大值
  19. int dfs(int u, int fa) {
  20.     for (int i = 0; i < h[u].size(); i++) {
  21.         int son = h[u][i].id;
  22.         int w = h[u][i].w;
  23.         if (son == fa) {
  24.             continue;
  25.         }
  26.         int t = dfs(son, u) + w;
  27.         if (t > dist[u][0]) {
  28.             dist[u][1] = dist[u][0];
  29.             dist[u][0] = t;
  30.         } else if (t > dist[u][1]) {
  31.             dist[u][1] = t;
  32.         }
  33.     }
  34.     return dist[u][0];  // 这里要返回最大值
  35. }
  37. int main() {
  38.     scanf("%d", &n);
  39.     for (int i = 0; i < n - 1; i++) {
  40.         int a, b, c;
  41.         scanf("%d%d%d", &a, &b, &c);
  42.         h[a].push_back({b, c});
  43.         h[b].push_back({a, c});
  44.     }
  46.     dfs(1, -1);
  47.     int s = 0;
  48.     for (int i = 1; i <= n; i++) {
  49.         s = max(dist[i][0] + dist[i][1], s);
  50.     }
  52.     printf("%lld\n", s * 10 + s * (s + 1ll) / 2);
  54.     return 0;
  55. }

1078. 旅游规划

W 市的交通规划出现了重大问题，市政府下定决心在全市各大交通路口安排疏导员来疏导密集的车流。
但由于人员不足，W 市市长决定只在最需要安排人员的路口安排人员。
具体来说，W 市的交通网络十分简单，由 n 个交叉路口和 n−1 条街道构成，交叉路口路口编号依次为 0,1,…,n−1
任意一条街道连接两个交叉路口，且任意两个交叉路口间都存在一条路径互相连接。
经过长期调查，结果显示，如果一个交叉路口位于 W 市交通网最长路径上，那么这个路口必定拥挤不堪。
所谓最长路径，定义为某条路径 p=(v1,v2,…,vk)，路径经过的路口各不相同，且城市中不存在长度大于 k 的路径（因此最长路径可能不唯一）。
因此 W 市市长想知道哪些路口位于城市交通网的最长路径上。
输入格式
第一行包含一个整数 n。
之后 n−1 行每行两个整数 u,v，表示编号为 u 和 v 的路口间存在着一条街道。
输出格式
输出包括若干行，每行包括一个整数——某个位于最长路径上的路口编号。
为了确保解唯一，请将所有最长路径上的路口编号按编号顺序由小到大依次输出。
数据范围
1≤n≤2×105
输入样例：
10
0 1
0 2
0 4
0 6
0 7
1 3
2 5
4 8
6 9
输出样例：
0
1
2
3
4
5
6
8
9

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  6. using namespace std;
  8. const int N = 200010, M = N * 2;
  10. int n;
  11. int h[N], e[M], ne[M], idx;
  12. int d1[N], d2[N], p1[N], up[N]; // p1[i] i节点向下走取最大值经过的儿子
  13. int maxd;
  15. void add(int a, int b)
  16. {
  17.     e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
  18. }
  20. void dfs_d(int u, int father)
  21. {
  22.     for (int i = h[u]; ~i; i = ne[i])
  23.     {
  24.         int j = e[i];
  25.         if (j != father)
  26.         {
  27.             dfs_d(j, u);
  28.             int distance = d1[j] + 1;
  29.             if (distance > d1[u])
  30.             {
  31.                 d2[u] = d1[u], d1[u] = distance;
  32.                 p1[u] = j;
  33.             }
  34.             else if (distance > d2[u]) d2[u] = distance;
  35.         }
  36.     }
  38.     maxd = max(maxd, d1[u] + d2[u]);
  39. }
  41. void dfs_u(int u, int father)
  42. {
  43.     for (int i = h[u]; ~i; i = ne[i])
  44.     {
  45.         int j = e[i];
  46.         if (j != father)
  47.         {
  48.             up[j] = up[u] + 1;
  49.             if (p1[u] == j) up[j] = max(up[j], d2[u] + 1);
  50.             else up[j] = max(up[j], d1[u] + 1);
  51.             dfs_u(j, u);
  52.         }
  53.     }
  54. }
  56. int main()
  57. {
  58.     scanf("%d", &n);
  59.     memset(h, -1, sizeof h);
  60.     for (int i = 0; i < n - 1; i ++ )
  61.     {
  62.         int a, b;
  63.         scanf("%d%d", &a, &b);
  64.         add(a, b), add(b, a);
  65.     }
  67.     dfs_d(0, -1);
  68.     dfs_u(0, -1);
  70.     for (int i = 0; i < n; i ++ )
  71.     {
  72.         int d[3] = {d1[i], d2[i], up[i]};
  73.         sort(d, d + 3);
  74.         if (d[1] + d[2] == maxd) printf("%d\n", i);
  75.     }
  77.     return 0;
  78. }

区间DP

282. 石子合并

设有 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. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  6. const int N = 310;
  7. int n,g[N],sum[N];
  8. int f[N][N];
  9. int main()
  10. {
  11.     cin >> n;
  12.     for (int i = 1; i <= n; i ++ ){
  13.         cin >> g[i];
  14.         sum[i] = sum[i-1] + g[i];
  15.     }
  16.     memset(f, 0x3f, sizeof f);
  17.     for (int i = 1; i <= n; i ++ ){
  18.         f[i][i]=0;
  19.     }
  20.     for(int len = 1; len < n; len++){
  21.         for(int i = 1; i + len <= n ;i++){
  22.             int j = i+len;
  23.             for (int k = i; k < j; k ++ ){
  24.                 f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);
  25.             }
  26.         }
  27.     }
  28.     cout << f[1][n];
  29. }

1222. 密码脱落

X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。
你的任务是：
给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。
输入格式
共一行，包含一个由大写字母ABCD构成的字符串，表示现在看到的密码串。
输出格式
输出一个整数，表示至少脱落了多少个种子。
输入样例1：
ABCBA
输出样例1：
0
输入样例2：
ABDCDCBABC
输出样例2：
3

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. using namespace std;
  5. int f[1010][1010];
  6. int main()
  7. {
  8.     string s;
  9.     cin >> s;
  10.     // 求最长回文串
  11.     int n = s.size();
  12.     for (int i = 0; i < n; i ++ ){
  13.         f[i][i]=1;
  14.     }
  15.     for (int i = n-1; i >= 0; i -- ){
  16.         for (int j = i+1; j < n; j ++ ){
  17.             if(s[i]==s[j]){
  18.                 f[i][j]=f[i+1][j-1]+2;
  19.             }else{
  20.                 f[i][j] = max(f[i+1][j],f[i][j-1]);
  21.             }
  22.         }
  23.     }
  24.     cout << n-f[0][n-1];
  25. }

1070. 括号配对

Hecy 又接了个新任务：BE 处理。
BE 中有一类被称为 GBE。
以下是 GBE 的定义：
空表达式是 GBE
如果表达式 A 是 GBE，则 [A] 与 (A) 都是 GBE
如果 A 与 B 都是 GBE，那么 AB 是 GBE
下面给出一个 BE，求至少添加多少字符能使这个 BE 成为 GBE。
注意：BE 是一个仅由(、)、[、]四种字符中的若干种构成的字符串。
输入格式
输入仅一行，为字符串 BE。
输出格式
输出仅一个整数，表示增加的最少字符数。
输入样例：
[])
输出样例：
1

本题与上一题不一样的地方

  1. 本题是必须两两匹配，上题是回文串就可以，即本题必须AA，而上一题一个A就行

因此上一题必须有如下初始化，而本题不应该有

  1.     int n = s.size();
  2.     for (int i = 0; i < n; i ++ ){
  3.         f[i][i]=1;
  4.     }
  1. 本题相当于可以多个部分接起来比如，即ABBACBBC在本题是可以的(因为可以拆成两部分ABBA和CBBC),但是在上一题求得的最长回文串是BBABB,

因此比上一题多了一个划分的过程

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. using namespace std;
  6. const int N = 110;
  7. int f[N][N];
  8. int main()
  9. {
  10.     string s;
  11.     cin >> s;
  12.     int n = s.size();
  13.     // 比起上题，本题这块不应该初始化
  14.     for (int i = n-2; i >=0 ; i -- ){
  15.         for (int j = i+1; j < n; j ++ ){
  16.             if(s[i]=='('&&s[j]==')'|| s[i]=='['&&s[j]==']'){
  17.                 f[i][j] = f[i+1][j-1]+2;
  18.             }else{
  19.                 f[i][j] = max(f[i+1][j],f[i][j-1]);
  20.             }
  21.             // 比求回文串多了下面这个
  22.             for (int k = i; k < j; k ++ ){
  23.                 f[i][j] = max(f[i][j],f[i][k]+f[k+1][j]);
  24.             }
  25.         }
  26.     }
  27.     cout << n - f[0][n-1];
  28. }

背包问题

4. 多重背包问题 I

有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  6. const int N = 110;
  7. int f[N];
  8. int v[N],w[N],s[N];
  9. int main()
  10. {
  11.     int n,m;
  12.     cin >> n >> m;
  13.     for (int i = 1; i <= n; i ++ ){
  14.         cin >> v[i] >> w[i] >> s[i];
  15.     }
  16.     for (int i = 1; i <= n; i ++ ){
  17.         for (int j = 1; j <= s[i]; j ++ ){ // 物品
  18.             for (int k = m; k ; k -- ){    // 体积
  19.                 if(v[i]<=k){
  20.                     f[k] = max(f[k],f[k-v[i]]+w[i]);
  21.                 }
  22.             }
  23.         }
  24.     }
  25.     cout << f[m];
  26. }

二进制优化
image.png

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 2000*1024,M = 2010;
  8. int f[M];
  9. int v[N],w[N];
  10. int main()
  11. {
  12.     int n,m,cnt=0;
  13.     cin >> n >> m;
  14.     for (int i = 0; i < n; i ++ ){
  15.         int a,b,s; // 体积,价值,数量
  16.         cin >> a >> b >> s;
  17.         int k=1;
  18.         while(k<s){
  19.             v[cnt] = k*a;
  20.             w[cnt] = k*b;
  21.             cnt++;
  22.             s-=k;
  23.             k*=2;
  24.         }
  25.         if(s>0){
  26.             v[cnt] = s*a;
  27.             w[cnt] = s*b;
  28.             cnt++;
  29.         }
  30.     }
  31.     n = cnt;
  32.     for (int i = 0; i < n; 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];
  39. }

3. 完全背包问题

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  6. const int N = 1010;
  8. int v[N],w[N];
  9. int f[N],g[N];
  10. int main()
  11. {
  12.     int n,m;
  13.     cin >> n >> m;
  14.     for (int i = 1; i <= n; i ++ ){
  15.         cin >> v[i] >> w[i];
  16.     }
  17.     for (int i = 1; i <= n; i ++ ){ // 物品
  18.         for (int j = v[i]; j <= m; j ++ ){ // 体积
  19.             f[j] = max(f[j],f[j-v[i]]+w[i]);
  20.         }
  21.     }
  23.     for (int i = 1; i <= m; i ++ ){ // 体积
  24.         for (int j = 1; j <= n; j ++ ) { // 物品
  25.             if(v[j]<=i){
  26.                 g[i] = max(g[i],g[i-v[j]]+w[j]);
  27.             }
  28.         }
  30.     }
  31.     //cout << f[m];
  32.     cout << g[m];
  33. }

9. 分组背包问题

有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。
接下来有 N 组数据：
每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <vector>
  5. #define x first
  6. #define y second
  7. using namespace std;
  8. typedef pair<int, int> PII;
  9. const int N = 110;
  10. int n,v;
  11. vector<PII>g[N];
  12. int f[N][N],t[N][N],h[N];
  13. int main()
  14. {
  15.     cin >> n >> v;
  16.     for (int i = 1; i <= n; i ++ ){
  17.         int s;
  18.         cin >> s;
  19.         for (int j = 0; j < s; j ++ ){
  20.             int a,b; // 体积，价值
  21.             cin >> a >> b;
  22.             g[i].push_back({a,b});
  23.         }
  24.     }
  26.     /*
  27.     f[i][k]的最大值
  28.         1. 从第i组里面一个也不选f[i-1][k]
  29.         2. 选择组内前一个物品取得最大值的方案 f[i][k]
  30.         3. 选择当前物品
  31.     */
  32.     for (int i = 1; i <= n; i ++ ){  // 组
  33.         for (int j = 0; j < g[i].size(); j ++ ){ // 每组的物品
  34.             for (int k = 1; k <= v; k ++ ){ // 体积
  35.                 if(k>=g[i][j].x){
  36.                     f[i][k] = max(f[i][k],max(f[i-1][k],f[i-1][k-g[i][j].x]+g[i][j].y));
  37.                 }else{
  38.                     f[i][k] = max(f[i-1][k],f[i][k]);
  39.                 }
  40.             }            
  41.         }
  42.     }
  43.     for (int i = 1; i <= n; i ++ ){ // 组
  44.         for (int j = v; j ; j -- ){ // 背包
  45.             t[i][j] = t[i-1][j];
  46.             for (int k = 0; k < g[i].size(); k ++ ){ // 物品
  47.                 if(g[i][k].x<=j){
  48.                     t[i][j] = max(t[i][j],t[i-1][ j-g[i][k].x ]+g[i][k].y);
  49.                 }
  50.             }
  51.         }
  52.     }
  54.     for (int i = 1; i <= n; i ++ ){ // 组
  55.         for (int j = v; j ; j -- ){ // 体积
  56.             for (int k = 0; k < g[i].size(); k ++ ){ // 物品
  57.                 if(j>=g[i][k].x){
  58.                     h[j] = max(h[j],h[j-g[i][k].x]+g[i][k].y);
  59.                 }
  60.             }
  61.         }
  62.     }
  63.     cout << h[v];
  64.     //cout << f[n][v];
  65.     //cout << t[n][v];
  66. }

1047. 糖果

由于在维护世界和平的事务中做出巨大贡献，Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。
在这一天，Dzx可以从糖果公司的 N 件产品中任意选择若干件带回家享用。
糖公司的 N 件产品每件都包含数量不同的糖果。
Dzx希望他选择的产品包含的糖果总数是 K 的整数倍，这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。
当然，在满足这一条件的基础上，糖果总数越多越好。
Dzx最多能带走多少糖果呢？
注意：Dzx只能将糖果公司的产品整件带走。
输入格式
第一行包含两个整数 N 和 K。
以下 N 行每行 1 个整数，表示糖果公司该件产品中包含的糖果数目，不超过 1000000。
输出格式
符合要求的最多能达到的糖果总数，如果不能达到 K 的倍数这一要求，输出 0。
输入样例：
5 7
1
2
3
4
5
输出样例：
14
样例解释
Dzx的选择是2+3+4+5=14，这样糖果总数是7的倍数，并且是总数最多的选择。

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  6. typedef long long LL;
  8. const int N = 1e5;
  9. int n,k;
  10. int a[N];
  11. int f[N][110]; // f[i][j] 前i个元素，余数为j的最大值
  13. int main()
  14. {
  15.     cin >> n >> k;
  16.     for (int i = 1; i <= n; i ++ ){
  17.         cin >> a[i];
  18.     }
  19.     memset(f, -0x3f, sizeof f); // 这里一定要将非法状态初始为-0x3f
  20.     f[0][0] = 0;   // 注意这里初始化
  21.     for (int i = 1; i <= n; i ++ ){
  22.         for (int j =0 ; j <k; j ++ ){
  23.             f[i][j] = max(f[i-1][j],f[i-1][(j+k-a[i]%k)%k]+a[i]);
  24.             //首先这里w%k是有可能比j大的，
  25.             //所以j+k，为什么还有（j+k-w%k）%k呢？因为j+k-w%k也是有可能比k大的，
  26.             //所以要%k
  27.         }
  28.     }
  29.     cout << f[n][0];
  31. }

1234. 倍数问题

众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。
但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。
现在小葱给了你 n 个数，希望你从这 n 个数中找到三个数，使得这三个数的和是 K 的倍数，且这个和最大。
数据保证一定有解。
输入格式
第一行包括 2 个正整数 n, K。
第二行 n 个正整数，代表给定的 n 个数。
输出格式
输出一行一个整数代表所求的和。
输入样例：
4 3
1 2 3 4
输出样例：
9
image.png
取模运算

  1. // 朴素的背包做法
  2. #include <iostream>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  6. const int N = 1e4;
  7. int f[N][4][10],n,K;
  8. int main()
  9. {
  10.     cin >> n >> K;
  11.     // 前i个数 模K余数为j 选k个数
  12.     memset(f, -0x3f, sizeof f);
  13.     for (int i = 0; i <= n; i ++ ){
  14.         f[i][0][0]=0;
  15.     }
  16.     for (int i = 1; i <= n; i ++ ){
  17.         int x;
  18.         cin >> x;
  19.         for (int k = 1; k <= 3; k ++ ){
  20.             for (int j = 0; j < K; j ++ ){
  21.                 f[i][k][j] = max(f[(i-1)][k][j],f[(i-1)][k-1][((j-x%K)+K)%K]+x);
  22.             }
  23.         }
  24.     }
  25.     cout << f[n][3][0];
  26. }

消去一维

  1. #include<iostream>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. const int N = 1e4+10;
  6. int f[4][1010]; // 选i个数，余数为j的最大值
  8. int n,K;
  9. int main(){
  10.     cin >> n >> K;
  11.     memset(f,-0x3f,sizeof f);
  12.     f[0][0]=0;
  13.     for(int i=1;i<=n;i++){
  14.         int x;
  15.         cin >> x;
  16.         for(int j=3;j;j--){
  17.             for(int k=0;k<K;k++){
  18.                 f[j][k] = max(f[j][k],f[j-1][(k-x%K+K)%K]+x);
  19.             }
  20.         }
  21.     }
  22.     cout<<f[3][0];
  23. }

贪心策略,由于和为最大，且模K余数为0，总共3个数，那么余数相同取最大值即可

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <vector>
  6. using namespace std;
  8. const int N = 1010;
  10. int n, m;
  11. vector<int> a[N]; // 模K余数为i的所有集合
  12. int f[4][N];
  14. int main()
  15. {
  16.     scanf("%d%d", &n, &m);
  18.     for (int i = 0; i < n; i ++ )
  19.     {
  20.         int x;
  21.         scanf("%d", &x);
  22.         a[x % m].push_back(x);
  23.     }
  25.     memset(f, -0x3f, sizeof f);
  26.     f[0][0] = 0;
  28.     for (int i = 0; i < m; i ++ ) // 枚举物品
  29.     {
  30.         sort(a[i].begin(), a[i].end());
  31.         reverse(a[i].begin(), a[i].end());
  33.         for (int u = 0; u < 3 && u < a[i].size(); u ++ ) // 枚举物品
  34.         {
  35.             int x = a[i][u];
  36.             for (int j = 3; j >= 1; j -- )     // 枚举体积
  37.                 for (int k = 0; k < m; k ++ )  // 余数
  38.                     f[j][k] = max(f[j][k], f[j - 1][(k - x % m + m) % m] + x);
  39.         }
  40.     }
  42.     printf("%d\n", f[3][0]);
  44.     return 0;
  45. }

900. 整数划分

一个正整数 n 可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中 n1≥n2≥…≥nk,k≥1。
我们将这样的一种表示称为正整数 n 的一种划分。
现在给定一个正整数 n，请你求出 n 共有多少种不同的划分方法。
输入格式
共一行，包含一个整数 n。
输出格式
共一行，包含一个整数，表示总划分数量。
由于答案可能很大，输出结果请对 109+7 取模。
输入样例:
5
输出样例：
7

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  6. const int N = 1010,MOD = 1e9+7;
  8. int f[N];
  9. int main(){
  10.     int n;
  11.     cin >> n;
  12.     f[0] = 1;
  13.     for (int i = 1; i <= n; i ++ ){ // 物品
  14.         for (int j = i; j <= n; j ++ ){ // 体积
  15.             f[j] =(f[j]+f[j-i])%MOD;
  16.         }
  17.     }
  18.     cout << f[n];
  21. }

1050. 鸣人的影分身

假设鸣人的查克拉能量为 M，他影分身的个数最多为 N，那么制造影分身时有多少种不同的分配方法？
注意：影分身可以分配0点能量。分配方案不考虑顺序，例如：M=7,N=3，那么 (2,2,3) 和 (2,3,2) 被视为同一种方案。
输入格式
第一行是测试数据的数目 t。
以下每行均包含二个整数 M 和 N，以空格分开。
输出格式
对输入的每组数据 M 和 N，用一行输出分配的方法数。
输入样例：
1
7 3
输出样例：
8
image.png
image.png

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  6. const int N = 15;
  7. int n,m;
  8. int f[N][N]; // 和为i 分成j个数
  10. int main()
  11. {
  12.     int T;
  13.     cin >> T;
  14.     while(T--){
  15.         cin >> m >> n; // 能量，影分身个数
  16.         f[0][0]=1;
  17.         for (int i = 0; i <= m; i ++ ){ // 这里要从0
  18.             for (int j = 1; j <= n; j ++ ){ // 这里要从1开始枚举
  19.                 f[i][j] = f[i][j-1];
  20.                 if(i-j>=0){
  21.                     f[i][j] += f[i-j][j];
  22.                 }
  23.             }
  24.         }
  25.         cout << f[m][n]<<endl;
  27.     }
  28. }

背包做法：

  1. 将总和看成体积
  2. 将分身个数看成体积

f[i][j][k]为前i个数中选，总和恰好为j，分身个数恰好为k的方案数 f[m][n]即为答案

  1. 同时本题为求组合数，所以先枚举物品再枚举体积，
  1. // 背包做法
  2. #include <iostream>
  3. #include <cstring>
  4. #include <algorithm>
  6. using namespace std;
  7. const int N = 110;
  8. int f[11][N]; //i个数 和为j 的方案数
  9. int main()
  10. {
  11.     int t;
  12.     cin >> t;
  13.     while (t -- ){
  14.         int m,n;  // 和为m，n为分身数量
  15.         cin >> m >> n;
  16.         memset(f, 0, sizeof f);
  17.         f[0][0]=1;
  18.         for (int i = 0; i <= m; i ++ ){ // 物品
  19.             for(int j=i;j <= m; j++){ // 一维体积
  20.                 for(int k=1; k<=n; k++){ // 二维体积
  21.                     f[j][k]+=f[j-i][k-1];
  22.                 }
  23.             }
  24.         }
  25.         cout << f[m][n]<<endl;
  26.     }
  27. }

1226. 包子凑数

小明几乎每天早晨都会在一家包子铺吃早餐。
他发现这家包子铺有 N 种蒸笼，其中第 i 种蒸笼恰好能放 Ai 个包子。
每种蒸笼都有非常多笼，可以认为是无限笼。
每当有顾客想买 X 个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有 X 个包子。
比如一共有 3 种蒸笼，分别能放 3、4 和 5 个包子。
当顾客想买 11 个包子时，大叔就会选 2 笼 3 个的再加 1 笼 5 个的（也可能选出 1 笼 3 个的再加 2 笼 4 个的）。
当然有时包子大叔无论如何也凑不出顾客想买的数量。
比一共有 3 种蒸笼，分别能放 4、5 和 6 个包子。
而顾客想买 7 个包子时，大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
输入格式
第一行包含一个整数 N。
接下来 N 行，每行包含一个整数 Ai。
输出格式
输出一个整数代表答案。
如果凑不出的数目有无限多个，输出INF。
输入样例1：
2
4
5
输出样例1：
6
输入样例2：
2
4
6
输出样例2：
INF
样例解释
对于样例1，凑不出的数目包括：1, 2, 3, 6, 7, 11。
对于样例2，所有奇数都凑不出来，所以有无限多个。

最大公约数，凑数问题
image.png
image.png
image.png
image.png
image.png
image.png

  1. 二维空间的写法（朴素写法）
  2. #include <cstdio>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 10010;
  9. int a[110];
  10. bool f[110][N];
  12. int gcd(int a, int b)
  13. {
  14.     return b ? gcd(b, a % b) : a;
  15. }
  17. int main()
  18. {
  19.     int n;
  20.     scanf("%d", &n);
  21.     int d = 0;
  22.     for (int i = 1; i <= n; i ++ )
  23.     {
  24.         scanf("%d", &a[i]);
  25.         d = gcd(d, a[i]);
  26.     }
  28.     if (d != 1) puts("INF");
  29.     else
  30.     {
  31.         f[0][0] = true;
  32.         for (int i = 1; i <= n; i ++ )
  33.             for (int j = 0; j < N; j ++ )
  34.             {
  35.                 f[i][j] = f[i - 1][j];
  36.                 if (j >= a[i]) f[i][j] |= f[i][j - a[i]];
  37.             }
  39.         int res = 0;
  40.         for (int i = 0; i < N; i ++ )
  41.             if (!f[n][i])
  42.                 res ++ ;
  44.         printf("%d\n", res);
  45.     }
  47.     return 0;
  48. }
  49. //优化完空间后的写法
  50. #include <cstdio>
  51. #include <algorithm>
  53. using namespace std;
  55. const int N = 10010;
  57. int a[110];
  58. bool f[N];
  60. int gcd(int a, int b)
  61. {
  62.     return b ? gcd(b, a % b) : a;
  63. }
  65. int main()
  66. {
  67.     int n;
  68.     scanf("%d", &n);
  69.     int d = 0;
  70.     for (int i = 1; i <= n; i ++ )
  71.     {
  72.         scanf("%d", &a[i]);
  73.         d = gcd(d, a[i]);
  74.     }
  76.     if (d != 1) puts("INF");
  77.     else
  78.     {
  79.         f[0] = true;
  80.         for (int i = 1; i <= n; i ++ )
  81.             for (int j = a[i]; j < N; j ++ )
  82.                 f[j] |= f[j - a[i]];
  84.         int res = 0;
  85.         for (int i = 0; i < N; i ++ )
  86.             if (!f[i])
  87.                 res ++ ;
  89.         printf("%d\n", res);
  90.     }
  92.     return 0;
  93. }

状态压缩DP

3494. 国际象棋

众所周知，“八皇后” 问题是求解在国际象棋棋盘上摆放 88 个皇后，使得两两之间互不攻击的方案数。
已经学习了很多算法的小蓝觉得 “八皇后” 问题太简单了，意犹未尽。作为一个国际象棋迷，他想研究在 N×MN×M 的棋盘上，摆放 KK 个马，使得两两之间互不攻击有多少种摆放方案。
由于方案数可能很大，只需计算答案除以 10000000071000000007 (即 109+7109+7) 的余数。
如下图所示，国际象棋中的马摆放在棋盘的方格内，走 “日” 字，位于 (x,y)(x,y) 格的马（第 xx 行第 yy 列）可以攻击 (x+1,y+2)(x+1,y+2)、(x+1,y−2)(x+1,y−2)、(x−1,y+2)(x−1,y+2)、(x−1,y−2)(x−1,y−2)、(x+2,y+1)(x+2,y+1)、(x+2,y−1)(x+2,y−1)、(x−2,y+1)(x−2,y+1) 和 (x−2,y−1)(x−2,y−1) 共 88 个格子。
image.png
输入格式
输入一行包含三个正整数 N,M,K,，分别表示棋盘的行数、列数和马的个数。
输出格式
输出一个整数，表示摆放的方案数除以 1000000007 的余数。

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 110, M = 1 << 6, K = 21, MOD = 1e9 + 7;
  9. int n, m, k;
  10. int f[N][M][M][K];
  11. // 求一个数的二进制中1的个数
  12. int get_count(int x)
  13. {
  14.     int res = 0;
  15.     while (x)
  16.     {
  17.         res ++ ;
  18.         x -= x & -x;
  19.     }
  20.     return res;
  21. }
  23. int main()
  24. {
  25.     cin >> n >> m >> k;
  26.     f[0][0][0][0] = 1;
  28.     int cnt = 0;
  29.     for (int i = 1; i <= m; i ++ )
  30.         for (int a = 0; a < 1 << n; a ++ )
  31.             for (int b = 0; b < 1 << n; b ++ )
  32.             {
  33.                 if (a & (b << 2) || b & (a << 2)) continue;
  34.                 for (int c = 0; c < 1 << n; c ++ )
  35.                 {
  36.                     if (c & (b << 2) || b & (c << 2)) continue;
  37.                     if (c & (a << 1) || a & (c << 1)) continue;
  38.                     int t = get_count(c);
  39.                     for (int u = t; u <= k; u ++, cnt ++ )
  40.                         f[i][b][c][u] = (f[i][b][c][u] + f[i - 1][a][b][u - t]) % MOD;
  41.                 }
  42.             }
  44.     int res = 0;
  45.     for (int i = 0; i < 1 << n; i ++ )
  46.         for (int j = 0; j < 1 << n; j ++ )
  47.             res = (res + f[m][i][j][k]) % MOD;
  49.     cout << res << endl;
  50.     return 0;
  51. }

291. 蒙德里安的梦想

求把 N×M 的棋盘分割成若干个 1×2 的的长方形，有多少种方案。
例如当 N=2，M=4 时，共有 5 种方案。当 N=2，M=3 时，共有 3 种方案。
如下图所示：
image.png
image.png

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. typedef long long LL;
  7. using namespace std;
  8. const int N = 15,M = 1<<N;
  10. LL f[N][M];
  11. int n,m;
  12. int st[M];
  13. bool check(int x){
  14.     int t=0;
  15.     for(int i=0;i<m;i++){
  16.         int j = x>>i&1;
  17.         if(j==0){
  18.             t++;
  19.         }else{
  20.             if(t&1){
  21.                 return false;
  22.             }
  23.         }
  24.     }
  25.     if(t&1){
  26.         return false;
  27.     }
  28.     return true;
  29. }
  31. int main(){
  33.     while(cin>>n>>m&&(n||m)){
  34.         memset(st, 0, sizeof st);
  35.         for(int i=0;i<1<<m;i++){
  36.             if(check(i)){
  37.                 st[i] = true;
  38.             }
  39.         }
  40.         memset(f, 0, sizeof f); // 多组测试数据，要清零
  41.         f[0][0] = 1;
  42.         for(int i=1;i <= n; i++){
  43.             for(int j = 0; j< 1<<m ;j++){
  44.                 for(int k = 0; k< 1<<m; k++){
  45.                     if((j&k)==0&&st[k|j]){
  46.                         f[i][j]+=f[i-1][k];
  47.                     }
  48.                 }
  49.             }
  50.         }
  51.         cout<< f[n][0]<<endl; // 这里为什么是f[n][0]呢
  52. /*
  53. f[i][j] 表示的是摆好前i行，伸到第i+1行的状态是j的方案数
  54. 那么为什么不能是摆好前i-1行，第i行的状态是j呢，我猜大概是
  55.     - 如果你摆好了前i-1行，第i行状态是j，那其实会影响到第i+1行的状态
  56.     还不太理解
  57. */
  58.     }
  59. }

91. 最短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. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. using namespace std;
  5. const int N = 21,M = 1<<N;
  7. int f[M][N];
  8. int w[N][N];
  10. int main()
  11. {
  12.     int n;
  13.     cin >> n;
  14.     for (int i = 0; i < n; i ++ ){
  15.         for (int j = 0; j < n; j ++ ){
  16.             cin >> w[i][j];
  17.         }
  18.     }
  19.     memset(f, 0x3f, sizeof f);
  20.     f[1][0]=0;
  21.     // f[i][j] 当前走过的点的集合是i，目前在j点的最小值是多少
  22.     // 是由f[i1][k] 转移过来的
  23.     // 那么i1是i集合减去j点的集合，然后沿着k->j走到j点
  24.     for (int i = 2; i < 1<<n; i ++ ){
  25.         for (int j = 0; j < n; j ++ ){
  26.             if((i>>j)&1){
  27.                 for (int k = 0; k < n; k ++ ){
  28.                     if((i>>k)&1&&k!=j){
  29.                         f[i][j] = min(f[i][j],f[i-(1<<j)][k]+w[k][j]);
  30.                         // 关键
  31.                     }
  32.                 }
  34.             }
  35.         }
  36.     }
  37.     cout << f[(1<<n)-1][n-1];
  39. }

902. 最短编辑距离

给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：
删除–将字符串 A 中的某个字符删除。
插入–在字符串 A 的某个位置插入某个字符。
替换–将字符串 A 中的某个字符替换为另一个字符。
现在请你求出，将 A 变为 B 至少需要进行多少次操作。
输入格式
第一行包含整数 n，表示字符串 A 的长度。
第二行包含一个长度为 n 的字符串 A。
第三行包含整数 m，表示字符串 B 的长度。
第四行包含一个长度为 m 的字符串 B。

  1. /*
  2. a b 两个串
  3. 对a插入相当于对b删除
  4. 对a替换相当于对a,b同时删除
  6. d[i][j] a的前i个字符和b的前j个字符匹配最小操作次数
  7. if a[i]==b[j]
  8.     d[i][j] = min(d[i][j],d[i-1][j-1])
  9. else
  10.     删除一个字符d[i-1][j],d[i][j-1]
  11.     替换一个字符d[i-1][j-1]
  12.     d[i][j] = min(d[i-1][j],d[i][j-1],d[i-1][j-1])+1
  13. */
  15. #include <iostream>
  16. #include <cstring>
  17. #include <algorithm>
  19. using namespace std;
  20. const int N = 1010;
  21. int f[N][N];
  22. int n,m,res;
  23. string a,b;
  24. int main()
  25. {
  26.     cin >> n >> a;
  27.     cin >> m >> b;
  28.     a = " "+a;
  29.     b = " "+b;
  31.     for (int i = 0; i <= n; i ++ ){
  32.         f[i][0] = i;
  33.     }
  34.     for (int i = 0; i <= m; i ++ ){
  35.         f[0][i] = i;
  36.     }
  37.     for (int i = 1; i <= n; i ++ ){
  38.         for (int j = 1; j <= m; j ++ ){
  39.             if(a[i]==b[j]){
  40.                 f[i][j] = f[i-1][j-1];
  41.             }else{
  42.                 f[i][j] = min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1;
  43.             }
  44.         }
  45.     }
  46.     cout << f[n][m];
  48. }

1212. 地宫取宝

X 国王有一个地宫宝库，是 n×m 个格子的矩阵，每个格子放一件宝贝，每个宝贝贴着价值标签。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。
走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是 k 件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 k 件宝贝。
输入格式
第一行 3 个整数，n,m,k，含义见题目描述。
接下来 n 行，每行有 m 个整数 Ci 用来描述宝库矩阵每个格子的宝贝价值。
输出格式
输出一个整数，表示正好取 k 个宝贝的行动方案数。
该数字可能很大，输出它对 1000000007 取模的结果。
输入样例1：
2 2 2
1 2
2 1
输出样例1：
2
输入样例2：
2 3 2
1 2 3
2 1 5
输出样例2：
14
image.png

  1. //本题核心点在于，将物品的价值范围从0到12改到1-13，为什么要这么做呢
  2. // 本题所拿物品价值应该是单调递增的顺序 f[i][j][cnt][0]，
  3. // if cnt==1 
  4. #include <iostream>
  5. #include <algorithm>
  7. using namespace std;
  9. const int N = 55;
  10. const int M = 15;
  11. const int MOD = 1e9 + 7;
  13. int n, m, c;
  14. int a[N][N];
  15. // f[i][j][cnt][k] 表示：在 (i, j) 这个点，拿了 cnt 个物品，这些物品中价值最大的是 k
  16. int f[N][N][M][M];
  18. int main() {
  19.   scanf("%d%d%d", &n, &m, &c);
  20.   for (int i = 1; i <= n; i++) {
  21.     for (int j = 1; j <= m; j++) {
  22.       scanf("%d", &a[i][j]);
  23.       a[i][j]++;
  24.     }
  25.   }
  26.   // 两个边界初始化
  27.   // 在起点 (1, 1) 处
  28.   // 如果拿也只能拿 a[i][j] 这个物品，只有一种方案
  29.   // 如果不拿，那就是 0 个物品，也是一个方案数
  30.   // 由于物品价值已经增加了一个偏移量，现在价值的范围是 [1, 13]
  31.   // 所以价值为 0 并不代表物品的价值，而是一个边界点
  32.   f[1][1][0][0] = 1;
  33.   f[1][1][1][a[1][1]] = 1;
  34.   for (int i = 1; i <= n; i++) {
  35.     for (int j = 1; j <= m; j++) {
  36.       for (int cnt = 0; cnt <= c; cnt++) {
  37.         for (int k = 0; k < M; k++) {
  38.           // 不拿物品
  39.           f[i][j][cnt][k] = (f[i][j][cnt][k] + f[i - 1][j][cnt][k]) % MOD;
  40.           f[i][j][cnt][k] = (f[i][j][cnt][k] + f[i][j - 1][cnt][k]) % MOD;
  41.           // 可以拿
  42.           if (cnt > 0 && k == a[i][j]) {
  43.             for (int s = 0; s < a[i][j]; s++) {
  44.               f[i][j][cnt][k] = (f[i][j][cnt][k] + f[i - 1][j][cnt - 1][s]) % MOD;
  45.               f[i][j][cnt][k] = (f[i][j][cnt][k] + f[i][j - 1][cnt - 1][s]) % MOD;
  46.             }
  47.           }
  48.         }
  49.       }
  50.     }
  51.   }
  52.   // 最后把在终点 (n, m) 处拿 c 个物品的方案数累加
  53.   int res = 0;
  54.   for (int i = 1; i < M; i++) {
  55.     res = (res + f[n][m][c][i]) % MOD;
  56.   }
  57.   printf("%d\n", res);
  58.   return 0;
  59. }

3420. 括号序列

给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。
两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。
例如，对于括号序列 ((()，只需要添加两个括号就能让其合法，有以下几种不同的添加结果：()()()、()(())、(())()、(()()) 和 ((()))。
输入格式
输入一行包含一个字符串 ss，表示给定的括号序列，序列中只有左括号和右括号。
输出格式
输出一个整数表示答案，答案可能很大，请输出答案除以 10000000071000000007 (即 109+7109+7) 的余数。
输入样例：
((()
输出样例：
5

image.png
image.png
image.png
思路（来自y总）
首先这个序列中我们需要添加的是左括号和右括号， 那么显然的我们要想左括号和右括号的添加是不是相互独立的呢？答案是肯定的：
image.png
考虑到我们只能在空隙中插入括号， 如果我们添加的一对左右括号不是在同一个空隙中， 那么他们显然是互不干扰的；如果是添加在同一个空隙中， 那么他们的添加顺序是唯一的， 只能是）（， 因为如果是（）的话， 那我们本次的添加就是无效的， 不满足添加最少的括号使得序列得到匹配。 由此可得， 我们只需要单独计算出添加左括号的方案数， 乘上单独添加右括号的方案数就是答案的数量。

明确了上面那个问题，我们就可以对左右括号进行单独计算了， 我们这里以添加左括号为例。

image.png

我们如果以右括号为端点， 将整个序列进行分割， 那么在分割后的每一小段添加左括号的方案数显然只和这段序列中左括号的数量有关， 因为这段序列里全是左括号， 怎么排列都是一种。所以我们只关注左括号的个数就好了， 更准确的来说， 我们只要关注我们添加的左括号的个数。

那么我们可以设计一个状态f[i][j]表示当前枚举到第i个右括号， 我们添加了j个左括号的==合法==方案（注意， 如果我们添加的操作使得前i个右括号都被匹配完后还有剩余的左括号， 我们仍认为这个状态是合法的）， 那么我们首先预处理出每个右括号前面至少需要添加的左括号的数量记为add数组，那么显然小于add的方案都是不合法的， 对于大于add的数量， 我们将添加的左括号分为两组， 一组在第i - 1个右括号的前面， 另一组在第i - 1个括号到第i个括号之间， 那么枚举任意一段的数目就可以实现转移了

  1. for(int i = add[1]; i <= len; i ++) f[1][i] = 1;//预处理， 很显然
  3. for(int i = 2; i <= num; i ++)
  4.     for(int j = add[i]; j <= len; j ++)//注意从add[i]开始， 比add[i]小的状态一定不合法
  5.         for(int k = 0; k <= j; k ++)//k表示的是i - 1到i段添加左括号的数量
  6.             f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;

这样我们的工作看似就完成了， 但是这个dp的时间复杂度是==n ^ 3==的， 过不了本题5k的数据， 那么我们就要考虑进行优化

我们可以明显注意到

  1. f[i][j] = f[i - 1][0] + f[i - 1][1] + ...... + f[i - 1][j]
  3. f[i][j + 1] = f[i - 1][0] + f[i - 1][1] + ...... + f[i - 1][j] + f[i - 1][j + 1]

那么我们可以得出

  1. f[i][j] = f[i][j - 1] + f[i - 1][j - 1]

那么我们只需要先O(n)的算出f[i][add[i]]， 后面的f[i][j]就都可以O(1)转移出了， 总体时间复杂度==n ^ 2==， 可以通过本题

当然对与添加右括号来说， 只需要将序列镜像翻转， 然后当作匹配左括号就可以了

  1. // 模拟求最少需要的左括号数量和右括号数量
  2. // 从前向后枚举，每遇到一个左括号cnt++,遇到一个右括号cnt--
  3. // 如果cnt小于0，就添加左括号，最后cnt的数量就是要添加的右括号的数量
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <algorithm>
  9. const int mod = 1e9 + 7;
  11. char s[5003];
  12. int f[5003][5003];
  13. int add[5003];
  14. int ans;
  16. int Work(int len)
  17. {
  18.     int lcnt = 0, rcnt = 0, num = 0; // 未被匹配的左， 右括号数， 右括号编号
  19.     memset(f, 0, sizeof(f));
  21.     for(int i = 1; i <= len; i ++)
  22.     {
  23.         if(s[i] == '(')
  24.             lcnt ++;
  25.         else
  26.         {
  27.             rcnt ++;
  28.             num ++;
  30.             if(lcnt) rcnt --, lcnt --;
  32.             add[num] = rcnt; // 记录最少需要添加的左括号的数量， add是单调不减的（虽然这个性质没用）
  33.         }
  34.     }
  36.     for(int i = add[1]; i <= len; i ++) f[1][i] = 1;
  37.     /* n ^ 3转移
  38.     for(int i = 2; i <= num; i ++)
  39.         for(int j = add[i]; j <= len; j ++)
  40.             for(int k = 0; k <= j; k ++)
  41.                 f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;
  42.     */
  43.     for(int i = 2; i <= num; i ++)
  44.     {
  45.         for(int j = 0; j <= add[i]; j ++) f[i][add[i]] = (f[i][add[i]] + f[i - 1][j]) % mod;
  47.         for(int j = add[i] + 1; j <= len; j ++) f[i][j] = (f[i][j - 1] + f[i - 1][j]) % mod;
  48.     }
  50.     return f[num][rcnt]; //返回答案
  51. }
  53. int main()
  54. {
  55.     scanf("%s", s + 1);
  56.     int len = strlen(s + 1);
  58.     ans = Work(len);
  60.     for(int i = 1; i <= len; i ++)// 镜像
  61.         if(s[i] == '(')
  62.             s[i] = ')';
  63.         else
  64.             s[i] = '(';
  66.     std:: reverse(s + 1, s + len + 1);//翻转
  68.     ans = 1LL * ans * Work(len) % mod;
  70.     printf("%d\n", ans);
  72.     return 0;
  73. }

1214. 波动数列

观察这个数列：
1 3 0 2 -1 1 -2 …
这个数列中后一项总是比前一项增加2或者减少3，且每一项都为整数。
栋栋对这种数列很好奇，他想知道长度为 n 和为 s 而且后一项总是比前一项增加 a 或者减少 b 的整数数列可能有多少种呢？
输入格式
共一行，包含四个整数 n,s,a,b，含义如前面所述。
输出格式
共一行，包含一个整数，表示满足条件的方案数。
由于这个数很大，请输出方案数除以 100000007 的余数。
输入样例：
4 10 2 3
输出样例：
2
样例解释
两个满足条件的数列分别是2 4 1 3和7 4 1 -2。
image.png

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  7. const int MOD = 100000007,N=1010;
  9. int n,s,a,b;
  10. int f[N][N];
  11. int main()
  12. {
  13.     cin >> n >> s >> a >> b;
  14.     int mod = (s % n+n)%n;
  16.     // 前i种物品，余数为j的方案
  17.     // 排列问题 先物品后背包
  18.     f[0][0] = 1;
  19.     for (int i = 1; i < n; i ++ ){    // 物品
  20.         int t;
  21.         for (int k = 0; k < 2; k ++ ){
  22.             if(k){
  23.                 t = a;
  24.             }else{
  25.                 t = -b;
  26.             }
  27.             for (int j = 0; j < n; j ++ ){ // 背包
  28.                 f[i][j] = (f[i][j] + f[i-1][(j-(i*t%n)%n+n)%n])%MOD;
  29.             }
  30.         }
  31.     }
  32.     cout << f[n-1][mod];
  33. }