本文最后更新于 2024年9月12日 晚上
常见的dp问题
1. 钢条切割问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<bits/stdc++.h>
#define m 10005
int p[10000005];
long long dp[m];
int a[m];
int s[m];
int num=0;
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&p[i]);
dp[i]=0;
}
dp[0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=i;j++){
if(dp[i-j]+p[j]>dp[i]){
dp[i]=dp[i-j]+p[j];
a[i]=j;
}
}
}
printf("%lld\n",dp[n]);
while(n>0){
s[num++]=a[n];
n=n-a[n];
}
printf("%d\n",num);
for(int i=0;i<num;i++){
printf("%d ",s[i]);
}
return 0;
}
|
2. 背包问题
有一个容量为V的背包，还有n个物体。现在忽略物体实际几何形状，我们认为只要背包的剩余容量大于等于物体体积，那就可以装进背包里。每个物体都有两个属性，即体积w和价值v。
问：如何向背包装物体才能使背包中物体的总价值最大？
背包的状态转移方程为
$dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[j])$
i代表对i件物体做决策，有两种方式—放入背包和不放入背包。
j表示当前背包剩余的容量。
转移方程的解释：
创建一个状态矩阵dp，横坐标 i 是物体编号，纵坐标 j 为背包容量。
首先将整个dp初始化为0，这个表示不放物体时最大价值为0 。（物体编号从1开始）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include<bits/stdc++.h>
int main(){
for(int i=1;i<=n;i++){
for(int j=v;j>=0;j--){
if(j>=w[i])
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
else
dp[i][j]=dp[i-1][j];
}
}
return 0;
}
|
背包问题的优化（空间复杂度）：
（1）状态表dp的遍历顺序为从第1行开始一行一行遍历，且在遍历第i行时候不会用到第i-2行数据，也就是i-2行及以前的数据没有用了，可以清除。同时，第i-1行的数据每个只会用到一次。
（2）遍历每一行时候只用到当前容量j和j-w[i]的数据，也就是第 i 次遍历只需要第 i-1 次遍历中容量小于等于 j 的数据。
（3）把遍历第i个物体和遍历第i-1个物体时的最大价值存在一个单元里。更新前f[j]存i-1的价值，更新后f[j]存i的价值。因为用不到i-2及以前的数据所以不需要存。因为以后不会再用到i-1的价值所以被覆盖了没问题
（4）j从背包容量V开始遍历，即从大到小遍历，保证了当前dp[j]和dp[j - w[i]]里面存的是i-1的数据。
1
2
3
4
5
6
7
8
| for (int i = 1; i <= n; i++)
{
for (int j = V; j >= w[i]; j--)
{
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
|
3. 矩阵连乘问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <bits/stdc++.h>
using namespace std;
long long dpmax[305][305];
long long dpmin[305][305];
int main(){
int n;
scanf("%d",&n);
int a[405];
for(int i=1;i<=n+1;i++){
scanf("%d",&a[i]);
}
for(int i=n-1;i>0;i--){
for(int j=i+1;j<=n;j++){
dpmin[i][j]=0x7f7f7f7f7f7f7f;
for(int k=i;k<j;k++){
dpmax[i][j]=max(dpmax[i][j],dpmax[i][k]+dpmax[k+1][j]+a[i]*a[k+1]*a[j+1]);
dpmin[i][j]=min(dpmin[i][j],dpmin[i][k]+dpmin[k+1][j]+a[i]*a[k+1]*a[j+1]);
}
}
}
printf("%.4lf",(double)dpmax[1][n]/dpmin[1][n]);
return 0;
}
|
4. 最长公共子串和最长公共子序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <stdio.h>
#include <string.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int dp[2005][2005];
int dp2[2005][2005];
int main() {
int T;
scanf("%d", &T);
while (T--) {
char S1[2001], S2[2001];
scanf("%s%s", S1, S2);
int len1 = strlen(S1);
int len2 = strlen(S2);
for (int i = 0; i <= len1; i++) {
dp[i][0] = 0;
dp2[i][0] = 0;
}
for (int j = 0; j <= len2; j++) {
dp[0][j] = 0;
dp2[0][j] = 0;
}
int maxLen = 0;
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (S1[i-1] == S2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = 0;
}
maxLen = MAX(maxLen, dp[i][j]);
dp2[i][j] = MAX(dp2[i-1][j], dp2[i][j-1]);
if (S1[i-1] == S2[j-1]) {
dp2[i][j] = MAX(dp2[i][j], dp2[i-1][j-1] + 1);
}
}
}
printf("%d %d\n", maxLen, dp2[len1][len2]);
}
return 0;
}
|
- 最长单调子序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
int lsrsa(const vector<int> &a) {
vector<int> sa;
for (auto x: a) {
if (sa.empty() || x > sa.back())
sa.push_back(x);
else
*lower_bound(sa.begin(), sa.end(), x) = x;
}
return (int) sa.size();
}
int lrsa(const vector<int> &a) {
vector<int> sa;
for (auto x: a) {
if (sa.empty() || x >= sa.back())
sa.push_back(x);
else
*upper_bound(sa.begin(), sa.end(), x) = x;
}
return (int) sa.size();
}
|