动态规划总结
一天，牛犇在森林里遇到了蒟蒻（本人），牛犇非常高兴，认为自己找到了有共同话题的人，于是，牛犇问蒟蒻。
牛犇：“你会动态规划吗？”
蒟蒻：“会那么一点点吧”
（蒟蒻拿出了01背包）
01背包
很经典的了，直接上例题吧
采药
题目描述：
松下问童子，言师采药去，云深不知处，只在此山中
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式：
第一行有两个整数T（1 ≤ T ≤ 1000）和M（1 ≤ M ≤ 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式：
包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
样例输入：
70 3
71 100
69 1
1 2
样例输出：
3
数据范围：
对于30%的数据，M ≤ 10；
对于全部的数据，M ≤ 100。
AC代码：
#include<bits/stdc++.h>
using namespace std;
int m,n,w[100010],c[100010],dp[110][1010];
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>w[i]>>c[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(j>=w[i]){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);
}else{
dp[i][j]=dp[i-1][j];
}
}
}
cout<<dp[n][m];
return 0;
}
其主要思路就是在中间的状态转移方程，和后面的输出
牛犇笑了笑
牛犇：“就这？01背包那个牛犇不会？”
蒟蒻：“牛犇别生气，我还有”
（蒟蒻慌张的拿出了其他背包）
其他背包
顾名思义，就是01背包以外的其他背包（说了像没说一样）
其他背包主要分为多重背包，完全背包，混合背包以及分组背包
多重背包和完全背包相对另外两种来说是基础的，其余两种则是基础背包结合在一起的
既然有这么多种背包那就多上几道例题吧
先来一道完全背包
疯狂的采药
题目描述：
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
这个山洞非常神奇，每株草药采摘后，会马上生长出一株同样的草药。
如果你是辰辰，你能完成这个任务吗？
输入格式：
第一行有2个整数T(1≤T≤1000)和M(1≤M≤100)，用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。
接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式：
1个整数，表示在规定的时间内可以采到的草药的最大总价值。
样例输入1：
70 3
71 100
69 1
1 2
样例输出1：
140
AC代码：
#include<bits/stdc++.h>
using namespace std;
int m,n,w[100010],c[100010],dp[110][1010];
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>w[i]>>c[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(j>=w[i]){
dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+c[i]);
}else{
dp[i][j]=dp[i-1][j];
}
}
}
cout<<dp[n][m];
return 0;
}
是不是很简单？多重背包也一样的（不用我废话了吧）
（蒟蒻为了活命临时给牛犇出的题目）
庆功宴
题目描述：
为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。
输入格式：
第一行二个数n(n<=500)，m(m<=6000)，其中n代表希望购买的奖品的种数，m表示拨款金额。
接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和购买的数量（买0件到s件均可），其中v<=100，w<=1000，s<=1000。
输出格式：
第一行：一个数，表示此次购买能获得的最大的价值。
样例输入1：
5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1
样例输出1：
1040
AC代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,v[100010],w[100010],s[100010],dp[100010];
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++){
if(j-k*v[i]<0){
break;
}
dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);
}
}
}
cout<<dp[m];
return 0;
}
哈哈，是不是特别”简单“，混合背包也来一个
混合背包
题目描述：
一个旅行者有一个最多能用V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，…,Wn，它们的价值分别为C1,C2,…,Cn。有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
输入格式：
第一行：二个整数，V(背包容量，V<=200)，N(物品数量，N<=30)；
第2…N+1行：每行三个整数Wi,Ci,Pi，前两个整数分别表示每个物品的重量，价值，第三个整数若为0，则说明此物品可以购买无数件，若为其他数字，则为此物品可购买的最多件数 (0≤Pi≤20) 。
输出格式：
仅一行，一个数，表示最大总价值。
样例输入：
10 3
2 1 0
3 3 1
4 5 4
样例输出：
11
提示：
选第一件物品1件和第三件物品2件。
AC代码：
#include<bits/stdc++.h>
using namespace std;
int v,n,w[100010],c[100010],p[100010],dp[100010];
int main(){
cin>>v>>n;
for(int i=0;i<n;i++){
cin>>w[i]>>c[i]>>p[i];
}
int ans=0;
for(int i=0;i<n;i++){
if(p[i]==0){
for(int j=w[i];j<=v;j++){
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
ans=max(ans,dp[j]);
}
}else{
for(int j=v;j>=w[i];j--){
for(int k=1;k<=p[i] && k*w[i]<=j;k++){
dp[j]=max(dp[j],dp[j-k*w[i]]+k*c[i]);
ans=max(ans,dp[j]);
}
}
}
}
cout<<ans;
return 0;
}
虽说吧，我觉得很难，但是其他的牛犇不会觉得（来自蒟蒻的自嘲）
其他背包就到这里
区间动态规划
接着顾名思义，就是在原来的基础上选一小段动态规划
没什么可说的，也不想说
直接上例题
石子合并
题目描述：
有N堆石子排成一排,其中第i堆的石子的重量为Ai，现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆合并成新的一堆，形成的新石子堆的重量以及消耗的体力是两堆石子的重量之和。
求把全部N堆石子合并成一堆最少需要消耗多少体力。
输入格式：
第一行一个正整数N（N<=300），表示石子的堆数N。
第二行N个正整数，表示每堆石子的质量(<=1000)。
输出格式：
一个正整数，表示最少需要消耗多少体力。
样例输入：
4
1 3 5 2
样例输出：
22
#include<bits/stdc++.h>
using namespace std;
int n,a[100010],dp[510][510],cnt[100010];
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
cnt[i]+=a[i]+cnt[i-1];
}
for(int i=n;i>=1;i--){
for(int j=i+1;j<=n;j++){
dp[i][j]=10000000;
for(int k=i;k<j;k++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+(cnt[j]-cnt[i-1]));
}
}
}
cout<<dp[1][n];
return 0;
}
牛犇：“还有吗？就这一点不够做啊”
蒟蒻（本人）：“呃呃呃，有”
（蒟蒻去找题目了）
（蒟蒻回来了）
（蒟蒻找到了线性动态规划）
线性动态规划
蒟蒻：“这一章是特殊加进来的，所以由我来讲解”
牛犇：“还有我”
蒟蒻：“线性动态规划就是将数组等动态规划”
牛犇：“比如最大子段和”
（牛犇拿出了最大子段和）
最大子段和
描述：
数组中子段的最大总和。
例如，1 2 3 -5 4 3 -6 中的最大子段总和是 1 + 2 + 3 +（ - 5）+ 4 + 3 = 8
输入格式：
第一行中的整数 n
第二行 n 个整数
输出格式：
一个整数表示最大字段和
样例输入：
7
1 2 3 -5 4 3 -6
样例输出：
8
AC代码：
#include<bits/stdc++.h>
using namespace std;
int n,a,mx=-10005;
int main(){
cin>>n;
int sum=0;
for(int i=1;i<=n;i++){
cin>>a;
sum+=a;
mx=max(sum,mx);
if(sum<0) sum=0;
}
cout<<mx;
return 0;
}
（蒟蒻被惊呆了）
（蒟蒻退出了聊天区）
牛犇：“好吧，虽然但是，还有一些题目，比如最大上升子序列”
最大上升子序列
题目描述：
对于一个数的序列bi，当b1<b2<…<bS的时候，我们称这个序列是上升的。
对于给定的一个序列(a1,a2,…,an)，我们可以找到一些上升的子序列(ai1,ai2,…,aiK)，这里1 <= i1 < i2 < … < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).
你的任务，就是对于给定的序列，求出最长上升子序列的长度。
输入格式：
第一行输入一个整数n
第二行输入n个整数
输出格式：
输出一个整数，表示最长递增子序列的长度
样例输入：
7
1 7 3 5 9 4 8
样例输出：
4
AC代码：
#include<bits/stdc++.h>
using namespace std;
int a[1005],cnt[1005],mx;
int main()
{
int n,i,j;
cin>>n;
for(i=1;i<=n;i++){
cin>>a[i];
cnt[i]=1;
for(j=1;j<i;j++){
if(a[j]<a[i]){
cnt[i]=max(cnt[i],cnt[j]+1);
}
mx=max(mx,cnt[i]);
}
}
cout<<mx;
return 0;
}
牛犇：“以及最长公共子序列”
题目描述：
给你两个字符串，求这两个串的最长公共子序列。
对于字符串abcde
acd，ace， ade等都是子序列，acb不是子序列
输入格式：
输入两行，每行包含一个字符串
输出格式：
输出一个整数表示最长公共子序列的长度
样例输入1：
xjoixjoi
joyjoy
样例输出1：
4
样例输入2：
xsrrnzkbhzkhzmvkjevsrbdiclckmsgpgngyckzvgysvwcgwayjokqactfxtivfbdwprufivtgg
zhbpvlxfkisdneogdseenjlewrobjhpppjczyxeaiqanaztksnpfwyhdjvipgwzznmnnxwraiiei
样例输出2：
21
AC代码：
#include <bits/stdc++.h>
using namespace std;
char a[1000];
char b[1000];
int maxlen[1000][1000]={0};
int main()
{
cin>>a>>b;
int la=strlen(a);
int lb=strlen(b);
for(int i=1;i<=la;i++){
maxlen[i][1]=0;
}
for(int i=1;i<=lb;i++){
maxlen[1][i]=0;
}
for(int i=1;i<=la;i++){
for(int j=1;j<=lb;j++){
if(a[i-1]==b[j-1]){
maxlen[i][j]=maxlen[i-1][j-1]+1;
}
else{
maxlen[i][j]=max(maxlen[i-1][j],maxlen[i][j-1]);
}
}
}
cout<<maxlen[la][lb]<<endl;
return 0;
}
（牛犇是不会告诉你这道题他CE了13次）
（蒟蒻加入了聊天区）
（蒟蒻退出了聊天区）
牛犇：“好了，结束了，也替蒟蒻和大家说声再见，bye”