第五讲 动态规划
5.1背包问题
5.1.1 2. 01背包问题
有 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
输出样例：
8
#include<bits/stdc++.h> using namespace std; const int N=1010; int f[N]; int v[N],w[N]; int n,m; 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]; return 0; }
5.1.2 3. 完全背包问题
有 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
#include<bits/stdc++.h> using namespace std; const int N=1010; int f[N]; int v[N],w[N]; int n,m; 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]; return 0; }
5.1.3 4. 多重背包问题 I
有 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
#include<bits/stdc++.h> using namespace std; 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=0;j<=m;j++) { for(int k=0;k<=s[i]&&k*v[i]<=j;k++) { f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k); } } } cout<<f[n][m]; return 0; }
5.1.4 5. 多重背包问题 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
#include<bits/stdc++.h> using namespace std; const int N=25000; int n,m; int v[N],w[N]; int f[N]; 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]; return 0; }
5.1.5 9. 分组背包问题
有 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
#include<bits/stdc++.h> using namespace std; const int N=110; int n,m; int v[N][N],w[N][N],s[N]; int f[N]; int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>s[i]; for(int j=0;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=0;k<s[i];k++) { if(v[i][k]<=j) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]); } } } cout<<f[m]; return 0; }
5.2线性DP
5.2.1 898. 数字三角形
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 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
#include<bits/stdc++.h> using namespace std; int n; int A[510][510],dp[510][510]; int main() { cin>>n; for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { cin>>A[i][j]; } } dp[1][1]=A[1][1]; for(int i=2;i<=n;i++) { for(int j=1;j<=i;j++) { if(j==1) { dp[i][j]=dp[i-1][j]+A[i][j]; } else if(j==i) { dp[i][j]=dp[i-1][j-1]+A[i][j]; } else { dp[i][j]=max(dp[i-1][j]+A[i][j],dp[i-1][j-1]+A[i][j]); } } } int ans=-1000000000; for(int i=1;i<=n;i++) { if(ans<dp[n][i]) { ans=dp[n][i]; } } cout<<ans; return 0; }
5.2.2 895. 最长上升子序列
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N 个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N≤1000，
−109≤数列中的数≤109
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4
#include<bits/stdc++.h> using namespace std; const int N=1010; int n; int a[N],f[N],st[N]; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { f[i]=1; for(int j=1;j<i;j++) { if(a[i]>a[j]) { f[i]=max(f[i],f[j]+1); } } } int ans=-1; for(int i=1;i<=n;i++) ans=max(ans,f[i]); cout<<ans; return 0; }
5.2.3 896. 最长上升子序列 II
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N 个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N≤100000，
−109≤数列中的数≤109
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; const int N=100010; int n; int a[N]; int q[N]; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; int len=0; q[0]=-2e9; for(int i=1;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]; } cout<<len; return 0; }
5.2.4 897. 最长公共子序列
给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数 N 和 M。
第二行包含一个长度为 N 的字符串，表示字符串 A。
第三行包含一个长度为 M 的字符串，表示字符串 B。
字符串均由小写字母构成。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N,M≤1000
输入样例：
4 5
acbd
abedc
输出样例：
3
#include<bits/stdc++.h> using namespace std; const int N=1010; int n,m; char a[N],b[N]; int f[N][N]; int main() { cin>>n>>m; cin>>a+1>>b+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]); if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1); } } cout<<f[n][m]; return 0; }
5.2.5 902. 最短编辑距离
给定两个字符串 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
#include<bits/stdc++.h> using namespace std; const int N=1010; int n,m; char a[N],b[N]; int f[N][N]; int main() { cin>>n>>a+1; cin>>m>>b+1; 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); } } cout<<f[n][m]; return 0; }
5.2.6 899. 编辑距离
给定 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
#include<bits/stdc++.h> using namespace std; const int N=1010,M=20; int n,m; char str[N][M]; int getOp(char a[],char b[]) { int f[M][M]; int lenA=strlen(a+1),lenB=strlen(b+1); for(int i=0;i<=lenB;i++) f[0][i]=i; for(int i=0;i<=lenA;i++) f[i][0]=i; for(int i=1;i<=lenA;i++) { for(int j=1;j<=lenB;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); } } return f[lenA][lenB]; } int main() { cin>>n>>m; for(int i=0;i<n;i++) { cin>>str[i]+1; } while(m--) { int op; char b[M]; cin>>b+1>>op; int ans=0; for(int i=0;i<n;i++) { if(getOp(str[i],b)<=op) ans++; } cout<<ans<<endl; } return 0; }
5.3区间DP
5.3.1 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≤N≤300
输入样例：
4
1 3 5 2
输出样例：
22
#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]; s[i]+=s[i-1]; } for(int len=2;len<=n;len++) { for(int i=1;i+len-1<=n;i++) { int j=i+len-1; f[i][j]=1e9; for(int k=i;k<j;k++) { f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]); } } } cout<<f[1][n]<<endl; return 0; }
