背包问题
01背包问题
每件物品最多只能用一次。
int n, m;
int v[N], w[N];
int f[N];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> 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]);
}
}
cout << f[m] << endl;
return 0;
}
完全背包问题
每件物品有无数个。
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i++){
for(int j = v[i]; j <= m; j++){
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[m] << endl;
return 0;
}
对比：第一个式子是01背包的状态转移，第二个是完全背包的。
多重背包问题
每个物品有s[i]个。
朴素算法
const int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];
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 = m; j >= 0; j--){
for(int k = 0; k <= s[i] && k * v[i] <= j; k++){
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
}
}
}
cout << f[n][m] << endl;
return 0;
}优化：把si拆分为1，2，4，...，2^k，c，然后转化为01背包问题。
const int N = 11010, M = 2010;
int n, m;
int v[N], w[N];
int f[M];
int main(){
cin >> n >> m;
int cnt = 0;
for (int i = 1; i <= n; i ++ ){
int a, b, s;
cin >> a >> b >> s;
int k = 1;
while(k <= s){
cnt++;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
if(s > 0){
cnt++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt;
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]);
}
}
cout << f[m] << endl;
return 0;
}分组背包问题
有N组，每组有若干种物品，每组只能选一个。
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];
int main(){
cin >> n >> m;
int cnt = 0;
for (int i = 1; i <= n; i++){
cin >> s[i];
for(int j = 1; j <= s[i]; j++){
cin >> v[i][j] >> w[i][j];
}
}
for(int i = 1; i <= n; i++){
for(int j = m; j >= 0; j--){
for(int k = 1; k <= s[i]; k++){
if(v[i][k] <= j) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
}
}
}
//朴素版：存的时候从1~s[i]存，然后比较的时候第三层循环从0~s[i]这样，当 k=0的时候，相当于就是f[i][j] = f[i - 1][j]了。
// for(int i = 1; i <= n; i++)
// for(int j = 0; j <= m; j++)
// for(int k = 0; k <= s[i]; k++)
// if(j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
cout << f[m] << endl;
return 0;
}
线性DP
数字三角形
最长上升子序列
O(n^2)
最长上升子序列Ⅱ
优化时间复杂度到O(nlogn)
https://www.acwing.com/video/328/
int n;
int a[N], q[N];
int main(){
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
int len = 0;
for(int i = 0; i < n; i++){
int l = 0, r = len;
while(l < r){
int mid = l + r + 1 >> 1;
if (q[mid] < a[i]) l = mid;
else r = mid - 1;
}
len = max(len, r + 1);
q[r + 1] = a[i];
}
printf("%d\n", len);
return 0;
}最长公共子序列
int n, m;
char a[N], b[N];
int f[N][N];
int main(){
cin >> n >> m;
int cnt = 0;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> b[i];
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]);
if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
}
printf("%d\n", f[n][m]);
return 0;
}最短编辑距离
https://www.acwing.com/video/334/
int main(){
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> m;
for (int i = 1; i <= m; i++) cin >> b[i];
//初始化.当a、b有一个长度为0时，只能通过加或删达到匹配
for (int i = 0; i <= m; i ++ ) f[0][i] = i;
for (int i = 0; i <= n; i ++ ) f[i][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);
}
}
printf("%d\n", f[n][m]);
return 0;
}编辑距离
https://www.acwing.com/video/331/
区间DP
石子合并问题
转移方程
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int n;
int s[N];
int f[N][N];
int main(){
cin >> n;
for (int i = 1; i <= n; i++) cin >> s[i];
for (int i = 1; i <= n; i ++ ) s[i] += s[i - 1]; //前缀和
for(int len = 2; len <= n; len++){
for(int i = 1; i + len - 1 <= n; i++){
int l = i, r = i + len - 1;
f[l][r] = 1e8;
//k枚举的是左半边最后一个石子的位置
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]);
}
}
printf("%d\n", f[1][n]);
return 0;
}计数类DP
整数划分 https://www.acwing.com/video/332/
方法一：
可以看作 容量为n，物品体积为1，2，3，...，n的完全背包问题，即每个数字可以选多次。
f(i,j)表示第1-i种物品的体积为j。第i种物品可以选任意个
int n;
int f[N]; //表示只从1~i中选，且总和等于j的方案数
int main(){
cin >> n;
f[0] = 1;
for(int i = 1; i <= n; i++){
for(int j = i; j <= n; j++){
f[j] = (f[j] + f[j - i]) % mod;
}
}
printf("%d\n", f[n]);
return 0;
}
方法二：
int n;
int f[N][N]; //f[i][j]表示总和为i，总个数为j的方案数
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;
printf("%d\n", res);
return 0;
}
数位统计DP
https://www.acwing.com/solution/content/52109/
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
/*
001~abc-1, 999
abc
1. num[i] < x, 0
2. num[i] == x, 0~efg
3. num[i] > x, 0~999
*/
int get(vector<int> num, int l, int r){
int res = 0;
for (int i = l; i >= r; i -- ) res = res * 10 + num[i];
return res;
}
int power10(int x){
int res = 1;
while (x -- ) res *= 10;
return res;
}
int count(int n, int x){
if (!n) return 0;
vector<int> num;
while (n){
num.push_back(n % 10);
n /= 10;
}
n = num.size();
int res = 0;
for (int i = n - 1 - !x; i >= 0; i -- ){
if (i < n - 1){
res += get(num, n - 1, i + 1) * power10(i);
if (!x) res -= power10(i);
}
if (num[i] == x) res += get(num, i - 1, 0) + 1;
else if (num[i] > x) res += power10(i);
}
return res;
}
int main(){
int a, b;
while (cin >> a >> b){
if(a == 0 && b == 0) break;
if (a > b) swap(a, b);
for (int i = 0; i <= 9; i ++ )
cout << count(b, i) - count(a - 1, i) << ' ';
cout << endl;
}
return 0;
}状态压缩DP
const int N = 12, M = 1 << N;
int n, m;
long long f[N][M];
bool st[M];
int main(){
while (cin >> n >> m){
if(n == 0 && m == 0) break;
for (int i = 0; i < 1 << n; i ++ ){
int cnt = 0;
st[i] = true;
for (int j = 0; j < n; j ++ )
if (i >> j & 1){
if (cnt & 1) st[i] = false;
cnt = 0;
}
else cnt ++ ;
if (cnt & 1) st[i] = false;
}
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 (int k = 0; k < 1 << n; k ++ )
if ((j & k) == 0 && st[j | k])
f[i][j] += f[i - 1][k];
cout << f[m][0] << endl;
}
return 0;
}这里还有状态压缩的写法，之后再看看
https://www.acwing.com/activity/content/code/content/64200/
最短Hamilton路径
memset(f, 0x3f, sizeof f);
f[1][0] = 0;
for(int i = 0; i < 1 << n; i++){
for(int j = 0; j < n; j++){
if(i >> j & 1){
for(int k = 0; k < n; k++){
if(i >> k & 1){
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
}
}
}
}
}树形DP
#include <bits/stdc++.h>
using namespace std;
const int N = 6010;
int n;
int h[N], e[N], ne[N], idx;
int happy[N];
int f[N][2];
bool has_fa[N];
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u){
f[u][1] = happy[u];
for (int i = h[u]; ~i; i = ne[i]){ // ~i ，等价于 i != -1
int j = e[i];
dfs(j);
f[u][1] += f[j][0];
f[u][0] += max(f[j][0], f[j][1]);
}
}
int main(){
cin >> n;
for (int i = 1; i <= n; i++) cin >> happy[i];
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i++){
int a, b;
cin >> a >> b;
add(b, a);
has_fa[a] = true;
}
int root = 1;
while (has_fa[root]) root++;
dfs(root);
printf("%d\n", max(f[root][0], f[root][1]));
return 0;
}记忆化搜索
int n, m;
int g[N][N];
int f[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dp(int x, int y){
int &v = f[x][y]; // 代表两者等价
if(v != -1) return v;
v = 1;
for(int i = 0; i < 4; i++){
int a = x + dx[i], b = y + dy[i];
if(a >= 1 && a <= n && b >= 1 && b <= m && g[x][y] > g[a][b])
v = max(v, dp(a, b) + 1);
}
return v;
}
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
cin >> g[i][j];
memset(f, -1, sizeof f);
int res = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
res = max(res, dp(i, j));
printf("%d\n", res);
return 0;
}
京公网安备 11010502036488号