动态规划是OI种经典的算法之一，用途较为广泛。
前言 动态规划是OI种经典的算法之一，用途较为广泛。
背包问题特点： 每种物品都有一个价值val和体积wei.
你现在有一个背包容积为V,你想用一些物品装背包使得物品总价值最大.
0-1背包 实现方法 状态转移方程：
由于$dp[i][ ]$只与$dp[i-1][ ]$有关，可以用滚动数组压掉第一维
或者：只开一个数组，直接在原数组上修改
由于$dp[i][j]$只与$dp[i-1]m $有关，如果仍然从前向后枚举j，会更改前面的值，对后续决策产生影响，所以我们需要从后往前枚举$j$，更新$j$的值
代码： 1 2 3 4 5 6 7 for(int i=1;i<=n;i++)//枚举装几个物品 { for(int j=v;j>=wei[i];j--)//枚举体积 { dp[j]=max(dp[j],dp[j-wei[i]]+w[i]); } }
典型题： P1048 采药
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 #include<cstdio> #include<iostream> using namespace std; int wei[105], val[105]; int dp[1005]; int main() { int t,m,res=-1; scanf("%d%d",&t,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&wei[i],&val[i]); } for(int i=1;i<=m;i++) { for(int j=t;j>=0;j--) { if(j>=wei[i]) { dp[j]=max(dp[j-wei[i]]+val[i], dp[j]); } } } printf("%d",dp[t]); return 0; }
完全背包 特点： 此类背包问题与01背包不同的是：我们的每种物品有无限多个,可重复选取。
实现方法 01背包中，为了防止更新时对后续更新产生影响，$t$要从后往前枚举。而完全背包只需改为从前往后即可。
代码： 1 2 3 4 5 6 7 for(int i=1;i<=n;i++)//枚举装几个物品 { for(int j=wei[i];j<=v;j++)//枚举体积 { dp[j]=max(dp[j],dp[j-wei[i]]+w[i]); } }
典型题： P1616 疯狂的采药
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include<cstdio> #include<cstring> using namespace std; long long f[1000001],v[1000001],h[1000001]; long long max(long long a,long long b) { if(a>b) return a; else return b; } int main() { long long i,j,m,n; scanf("%ld %ld",&m,&n); for(i=1;i<=n;i++) scanf("%ld %ld",&h[i],&v[i]); for(i=1;i<=n;i++) for(j=h[i];j<=m;j++) f[j]=max(f[j],f[j-h[i]]+v[i]); printf("%ld\n",f[m]); return 0; }
多重背包 线性动归 线性动归特点： 只在一个数列上的dp。
实现方法 用$dp[i]$代表到$i$为止最优策略。
典型题 最长不下降子序列：
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 #include<iostream> using namespace std; int a[100000]; int dp[1000000]; int main() { int n; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; dp[i]=1; } for(int i=1;i<=n;i++) { for(int j=1;j<i;j++) { if(a[i]>=a[j])//可以更新 { dp[i]=max(dp[i],dp[j]+1);//取所有可以更新的情况中，更新后的最优决策（即最大值） } } } int ans=0; for(int i=1;i<=n;i++) { ans=max(ans,dp[i]); } cout<<ans; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include<cstdio> #include<algorithm> #include <iostream> using namespace std; int n,a[105],f[2][105],ans; int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) for(int j=0;j<i;j++) if(a[i]>a[j]) f[0][i]=max(f[0][i],f[0][j]+1); a[n+1]=0; for(int i=n;i;i--) for(int j=n+1;j>i;j--) if(a[i]>a[j]) f[1][i]=max(f[1][i],f[1][j]+1); for(int i=1;i<=n;i++) ans=max(f[0][i]+f[1][i]-1,ans); printf("%d\n",n-ans); return 0; }
导弹拦截
友好城市
区间动归 区间动归特点：
实现方法 用$dp[i][j]$代表区间$[i,j]$的最大值；
典型题： P1880 [NOI1995]石子合并
树形动归 树形动归特点： 在一棵树上的动态规划
实现方法 类比P1216 [USACO1.5]数字三角形 Number Triangles
数字三角形代码：
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 #include<iostream> using namespace std; int a[10000][10000]; int main() { int n; cin>>n; int num=0; for(int i=0;i<n;i++) { for(int j=0;j<=i;j++) { cin>>a[i][j]; } } int j=0; for(int i=n-2;i>=0;i--) { for(int j=0;j<=i;j++) { if(a[i+1][j]>=a[i+1][j+1]) { a[i][j]+=a[i+1][j]; } else { a[i][j]+=a[i+1][j+1]; } } } cout<<a[0][0]; }
树形动归与这个类似，应该从树的底部开始，向上处理
程序实现 如何存树： 利用链式前向星把树存成无向图
1 2 3 4 5 6 7 int head[1666],pre[3666],to[3666],cnt=0; void add_edge(int a,int b) { to[++cnt]=b; pre[cnt]=head[a]; head[a]=cnt; }
详细解释：链式前向星
如何从底部向上动归： 递归实现
1 2 3 4 5 6 7 8 9 10 11 12 void treedp(int pos)//pos是现在的位置 { vis[pos]=1;//标记已访问过 for(int i=head[pos];i!=-1;i=pre[i])//链式前向星的遍历 { if(!vis[to[i]])//第一次到达（防止在返回过程中再次递归下去，形成死循环） { treedp(to[i]);//递归到下一层 ···//状态转移方程 } } }
典型题 P1352 没有上司的舞会
代码：
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 42 43 #include<iostream> #include<cstring> #include<cstdio> using namespace std; int f[5][6000]; int n,b,a,root; int cun[12000],zhi[12000],geshu[12000]; bool vis[100000]; void dp(int x) { vis[x]=1; for(int i=zhi[x];i;i=cun[i]) { if(vis[i]==0) { dp(i); f[1][x]=max(max(f[1][x],f[0][i]+f[1][x]),f[0][i]); f[0][x]=max(max(f[0][x],f[1][i]+f[0][x]),max(f[1][i],f[0][i])); } } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&f[1][i]); for(int i=1;i<=n;i++) { scanf("%d%d",&a,&b); geshu[a]++; cun[a]=zhi[b]; zhi[b]=a; } for(int i=1;i<=n;i++) if(geshu[i]==0) { root=i; break; } dp(root); printf("%d",max(f[1][root],f[0][root])); return 0; }
P2016 战略游戏
代码：
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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,a,b,c,cnt,head[1666],f[1666][2]; struct edge { int to; int next; }edge[3333]; void add_edge(int x,int y) { ++cnt; edge[cnt].to=y; edge[cnt].next=head[x]; head[x]=cnt; } void tree(int x,int from) { f[x][1]=1; f[x][0]=0; if(head[x]==0) { f[x][0]=10000000; } for(int i=head[x];i;i=edge[i].next) { if(edge[i].to!=from) { tree(edge[i].to,x); f[x][1]+=min(f[edge[i].to][1],f[edge[i].to][0]); f[x][0]+=f[edge[i].to][1]; } } } int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a>>b; a++; for(int j=1;j<=b;j++) { cin>>c; c++; add_edge(a,c); add_edge(c,a); } } tree(1,0); int ans=min(f[1][1],f[1][0]); printf("%d",ans); }
状压动归 状压动归特点： 一般在矩阵上进行动归，不过由于情况过多，不可以开inf维数组进行解决，就需要使用状态压缩动归。在这类动态规划中，每个点的状态往往只用0或1来表示（复杂一些的可能需要用0,1,2），每一行每个点上的数字可以连成一个01串，如果我们把它看成一个二进制数，即可用一个十进制数来表示复杂的状态，即状态压缩。
实现方法
用十进制数表示一个状态，对每一个合法的状态（十进制数字）进行处理（通过位运算）
由于限制了摆放k个，所以需要统计当前状态摆放了几个（二进制中1的个数）
先进行预处理，将可能方案（用一个十进制数表示）存入数组，将这个方案中1的个数存入数组，顺便简要删除一些不可行的方案，降低复杂度，然后在剩余方案上进行动归。
典型题 P1896 [SCOI2005]互不侵犯
题意分析
一个$nn$的矩阵，有多少种方式，不重叠地摆放k个$3 3$的方块，要求输出方案数。
处理方块中心点位置，看中心点放在某个位置是否合法（它的上下左…八个方向有没有其他方块）
根据两个方块中心点一定不相邻，删掉一些方案预处理 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 void prepare()//预处理可用情况 { int k; s0=0; ans=0; memset(f,0,sizeof(f)); for(int i=0;i<(1<<n);i++)//十进制数从0枚举到 1<<n，即可把所有状态处理全 { if(i&(i<<1))continue;//如果这个方案中有两个相邻，一定不满足条件，略过 k=0;//计数器 for(int j=0;j<n;j++)//------ {// 统 if(i&(1<<j))// 计 {// 1的 k++;// 个 }// 数 }// ------ s[++s0]=i; num[s0]=k; } }
