背包问题
多重背包
1019.庆功会 https://www.acwing.com/activity/content/problem/content/1275/
完全背包
532.货币系统 https://www.acwing.com/problem/content/534/ 筛法 + 最大无关向量组
混合背包
7.混合背包问题 https://www.acwing.com/problem/content/7/
有依赖的背包问题, 树上dp + 背包 | 二进制状压 + 分组背包
10.有依赖的背包问题 https://www.acwing.com/problem/content/10/
487.金明的预算方案 https://www.acwing.com/problem/content/description/489/
二维费用背包问题
8.二维费用的背包问题 https://www.acwing.com/problem/content/8/
1022.宠物小精灵之收服 https://www.acwing.com/problem/content/1024/
二维费用'不少于'问题
1020.潜水员 https://www.acwing.com/problem/content/1022/
记录路径背包问题
1013.机器分配https://www.acwing.com/problem/content/1015/
12.背包问题求具体方案 https://www.acwing.com/problem/content/12/
求最优解方案数
11.背包问题求方案数 https://www.acwing.com/problem/content/11/
计数类背包问题
278.数字组合 https://www.acwing.com/problem/content/280/
1023.买书 https://www.acwing.com/problem/content/1025/
1021.货币系统 https://www.acwing.com/problem/content/1023/
P2946 [USACO09MAR]Cow Frisbee Team S https://www.luogu.com.cn/problem/P2946
倍数 + 更好的理解为什么不能用滚动数组
拓展变形练习
P1156 垃圾陷阱 https://www.luogu.com.cn/problem/P1156 01背包变形
P5322 [BJOI2019] 排兵布阵 https://www.luogu.com.cn/problem/P5322 分组背包变形
2022杭电多校1Backpack https://acm.hdu.edu.cn/showproblem.php?pid=7140 01背包 + bitset优化
线性DP
LIS最长上升子序列
896.最长上升子序列 II https://www.acwing.com/problem/content/898/
好的LIS贪心模板
memset(a, 0x3f, sizeof a);
int r = a[0];
for (int i = 0; i < n; i ++ )
{
int x = nums[i];
*lower_bound(a, a + n, x) = x;
}
while (a[res] != r) res ++;
最短编辑距离
902.最短编辑距离 https://www.acwing.com/problem/content/904/
状态机DP
1049.大盗阿福 https://www.acwing.com/problem/content/1051/
1055.股票买卖 II https://www.acwing.com/problem/content/description/1057/
区间DP
基础区间DP
479.加分二叉树 https://www.acwing.com/problem/content/481/
1069.凸多边形的划分 https://www.acwing.com/problem/content/1071/
二维区间DP
321.棋盘分割https://www.acwing.com/problem/content/323/
环状区间DP
1068.环形石子合并 https://www.acwing.com/problem/content/1070/
320.能量项链 https://www.acwing.com/problem/content/322/
树形DP
基础树形DP
1072.树的最长路径 https://www.acwing.com/problem/content/1074/
题解： 以每个节点u为根节点子树的最长和次长深度之和
1075.数字转换 https://www.acwing.com/problem/content/1077/
题解：建图 + 树的最长路径
换根dp
1073.树的中心 https://www.acwing.com/problem/content/1075/
题解：两次dfs：第一次dfs找到子节点最长， 第二次dfs找到父节点最长
有依赖背包dp
1074.二叉苹果树 https://www.acwing.com/problem/content/description/1076/
cf/atc dp题
Codeforces Round #734 (Div. 3) E. Fixed Points
https://codeforces.com/contest/1551/problem/E
题意：
你可以删除任意一个数并且合并左右， 求数次操作后元素的数值与下标相同(a[i] == i)的个数大于等于k的最少操作数
题解：
/*f(i, j)前i个，删除j个数, 最大匹配数
f(i, j) =
f(i - 1, j) + p[i] == j ? 1 : 0 前面删除的数的个数 == 该数要匹配需要移动的数
f(i - 1, j - 1);
*/
代码：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 2010;
int a[N], p[N], f[N][N];
void sovle()
{
memset(f, 0, sizeof f);
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i ++ )
scanf("%d", &a[i]);
//预处理各个位置上的数回到匹配位置要移动的步数
for (int i = 1; i <= n; i ++ )
p[i] = i - a[i];
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= i; j ++ )
{
if (j >= 1) f[i][j] = max(f[i][j], f[i - 1][j - 1]);
if (j < i) f[i][j] = max(f[i][j], f[i - 1][j] + (p[i] == j ? 1 : 0));
}
int res = -1;
for (int i = 0; i <= n; i ++ )
if (f[n][i] >= k) {res = i; break;}
printf("%d\n", res);
}
int main()
{
int t;
scanf("%d", &t);
while (t -- )
sovle();
return 0;
}
AtCoder Beginner Contest 271D - Flip and Adjust
https://atcoder.jp/contests/abc271/tasks/abc271_d
题意：
n组,每组2个数，每组选一个数使得和为m,输出方案
题解：
分组背包
f(i, j) |= f(i - 1, j - a[i]);
f(i, j) |= f(i - 1, j - a[i]);
代码:
dp[0][0] = true;
for (int i = 1; i <= n; i ++ )
{
for (int j = 0; j <= m; j ++ )
{
if (j >= a[i] && dp[i - 1][j - a[i]])
{
dp[i][j] |= dp[i - 1][j - a[i]];
st[i][j] = {j - a[i], true};
}
else if (j >= b[i] && dp[i - 1][j - b[i]])
{
dp[i][j] |= dp[i - 1][j - b[i]];
st[i][j] = {j - b[i], false};
}
}
}
if (!dp[n][m]) cout << "No";
else
{
cout << "Yes" << endl;
vector<bool> ans;
for (int i = n, j = m; i > 0; i -- )
{
ans.push_back(st[i][j].second);
j = st[i][j].first;
}
for (auto it = ans.rbegin(); it < ans.rend(); it ++ )
cout << (*it ? 'H' : 'T');
}
cout << endl;
