|
一、背包DP
背包是初学动态规划的经典模型，附：背包九讲
1【NOIP2018】货币系统 【完全背包】
题意：给定一个包含n个元素的集合A，求一个最小的子集B使得A能表示的数B也能表示，A不能表示的数B也不能表示
首先因为B是A的子集，所以A不能表示的数B一定不能表示。因此只需要处理能表示的数即可
要求A表示的数B也能表示的最小子集B，说明什么呢？如果A中的一个元素x可以被A中其他的元素表示，那么这个x就不是必需的了
也就是说，我们要求这个集合里哪些元素不可以被集合里的其他元素表示，用完全背包求方案数即可
#include <bits/stdc++.h>
using namespace std;
int n,t,f[5000005],dp[5000005],ans;
int main(){
scanf("%d",&t);
while(t--){
memset(dp,0,sizeof(dp));memset(f,0,sizeof(f));ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&f[i]);
sort(f+1,f+1+n);dp[0]=1;
for(int i=1;i<=n;i++){
if(!dp[f[i]])ans++;
for(int j=f[i];j<=f[n];j++)dp[j]+=dp[j-f[i]];
}
printf("%d\n",ans);
}
return 0;
}
2 【NOIP2014】飞扬的小鸟 【完全背包+01背包】
题意：二维平面， k个管道。小鸟每个单位时间右移 1，竖直方向：若点击屏幕，上升高度x，单位时间可点多次，效果叠加；若不点击屏幕，下降 y。高度为0或碰到管道，游戏失败。高度为 m 时，无法再上升。若可以完成，求最少点击屏幕数；否则，求小鸟最多可以通过多少个管道缝隙
根据题意，小鸟一个单位时间内向上条的次数是无限制的（除非碰到顶层），那么上升其实就是完全背包问题，背包容量就是当前小鸟飞到的高度。而在一个单位时间内，小鸟最多只能下降一次，那么下降就是01背包问题
设f[i][j]表示当前小鸟飞到(i,j)时的最少跳跃次数，考虑怎么转移
- 如果是上升：那么当前位置可能是（1）由前一个单位时间内的j-x[i]跳了一次得来的 （2）由现在的j-x[i]跳了一次得来的
- 如果是下降：那么当前位置是（1）不跳（保持现在的位置）（2）由前一个单位时间内的j+y[i]得来的
- 如果是在顶层：讲向上跳时溢出m高度的状态与自己比较取最小值
- 如果无法通过：赋极大值
#include <bits/stdc++.h>
using namespace std;
int n,m,k,x[10005],y[10005],b[10005],t[10005],f[10005][2005],ans=0x3f3f3f3f;
bool flag[10005];
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
for(int i=1;i<=n;i++)t[i]=m,b[i]=1;
for(int i=1,xx,yy,zz;i<=k;i++){
scanf("%d%d%d",&xx,&yy,&zz);
flag[xx]=1;b[xx]=yy+1;t[xx]=zz-1;
}
memset(f,0x3f,sizeof(f));
for(int i=1;i<=m;i++)f[0][i]=0;
for(int i=1;i<=n;i++){
for(int j=x[i]+1;j<=x[i]+m;j++)
f[i][j]=min(f[i-1][j-x[i]]+1,f[i][j-x[i]]+1);
for(int j=m+1;j<=x[i]+m;j++)
f[i][m]=min(f[i][m],f[i][j]);
for(int j=1;j<=m-y[i];j++)
f[i][j]=min(f[i][j],f[i-1][j+y[i]]);
for(int j=1;j<=b[i]-1;j++)f[i][j]=0x3f3f3f3f;
for(int j=t[i]+1;j<=m;j++)f[i][j]=0x3f3f3f3f;
}
for(int i=1;i<=m;i++)ans=min(ans,f[n][i]);
if(ans<0x3f3f3f3f){printf("1\n%d\n",ans);return 0;}
int i,j;
for(i=n;i>=1;i--){
for(j=1;j<=m;j++)
if(f[i][j]<0x3f3f3f3f)break;
if(j<=m)break;
}
ans=0;for(j=1;j<=i;j++)if(flag[j])ans++;
printf("0\n%d\n",ans);
return 0;
}
二、线性DP
3 【NOIP2015】子串 【计数类DP】
题意：从字符串A中取出 k个互不重叠的非空子串，然后把这 k个子串按照其在字符串 A中出现的顺序依次连接得到一个新串。求有多少种方案使这个新串与字符串 B相等？
设
f
[
i
]
[
j
]
[
k
]
f[i][j][k]
f[i][j][k] 表示A串选到
a
[
i
]
a[i]
a[i]（
a
[
i
]
a[i]
a[i] 被选），B串选到
b
[
j
]
b[j]
b[j]（
b
[
j
]
b[j]
b[j] 之前的和
b
[
j
]
b[j]
b[j] 都被选）时分成k段选取共有多少种选法。前缀和数组
g
[
i
]
[
j
]
[
k
]
g[i][j][k]
g[i][j][k] 表示A串选到
a
[
i
]
a[i]
a[i] (
a
[
i
]
a[i]
a[i] 与之前怎么选都行）,B串选到
b
[
j
]
b[j]
b[j] （
b
[
j
]
b[j]
b[j] 之前和
b
[
j
]
b[j]
b[j] 都被选）的时候分成
k
k
k 段选取所有方案的和
考虑
f
f
f 的转移
- 若
a
[
i
]
≠
b
[
j
]
a[i]≠b[j]
a[i]?=b[j]：
f
[
i
]
[
j
]
[
k
]
=
0
f[i][j][k]=0
f[i][j][k]=0,因为如果
a
[
i
]
≠
b
[
j
]
a[i]≠b[j]
a[i]?=b[j]，那么
a
[
i
]
a[i]
a[i] 被选的话是不可能有方案的
- 若
a
[
i
]
=
b
[
j
]
a[i]=b[j]
a[i]=b[j]：
f
[
i
]
[
j
]
[
k
]
=
f
[
i
?
1
]
[
j
?
1
]
[
k
]
+
g
[
i
?
1
]
[
j
?
1
]
[
k
?
1
]
f[i][j][k]=f[i-1][j-1][k]+g[i-1][j-1][k-1]
f[i][j][k]=f[i?1][j?1][k]+g[i?1][j?1][k?1]
（1）可以把
a
[
i
]
a[i]
a[i],
b
[
j
]
b[j]
b[j] 与
a
[
i
?
1
]
a[i-1]
a[i?1],
b
[
j
?
1
]
b[j-1]
b[j?1] 看做一个整体，这样的话也就只有一种方案就是
f
[
i
?
1
]
[
j
?
1
]
[
k
]
f[i-1][j-1][k]
f[i?1][j?1][k]，因为
g
g
g的定义是
a
[
i
]
a[i]
a[i] 可能选或不选的方案和，但
a
[
i
]
a[i]
a[i] 必选
（2）可以把
a
[
i
]
a[i]
a[i],
b
[
j
]
b[j]
b[j] 看做一个单独的部分，这样方案就会多上
g
[
i
?
1
]
[
j
?
1
]
[
k
?
1
]
g[i-1][j-1][k-1]
g[i?1][j?1][k?1] ，因为看做单独的部分的话，相当于
a
[
i
?
1
]
a[i-1]
a[i?1] (
a
[
i
?
1
]
a[i-1]
a[i?1]选或不选)
b
[
j
?
1
]
b[j-1]
b[j?1] 每一个可行方案后面加上一个匹配的
a
[
i
]
a[i]
a[i],
b
[
j
]
b[j]
b[j]
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int f[205][205],g[205][205],n,m,kk;
char a[1005],b[1005];
int main(){
scanf("%d%d%d",&n,&m,&kk);
cin>>a+1;cin>>b+1;g[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=m;j>=1;j--){
for(int k=kk;k>=1;k--){
if(a[i]==b[j])f[j][k]=(f[j-1][k]+g[j-1][k-1])%mod;
else f[j][k]=0;
g[j][k]=(g[j][k]+f[j][k])%mod;
}
}
}
printf("%d\n",g[m][kk]);
return 0;
}
三、区间DP
区间dp在【NOIP2006】能量项链，【NOIP2007】矩阵取数游戏 有考过，2021csp-s也有考到（4道题2道区间dp ），前两道题都属于区间dp的经典板子题，这里不再赘述，2021年csp-s区间dp题的分析蒟蒻也有写过 戳这里查看~
四、状压DP
4【NOIP2017】宝藏
题意：给n个点，m条边，要选一个点作根建一棵生成树满足代价最小，一棵生成树的代价是所有
d
e
p
[
i
]
?
d
i
s
[
f
a
[
i
]
]
[
i
]
dep[i]*dis[fa[i]][i]
dep[i]?dis[fa[i]][i]的和
f
[
s
]
[
u
]
[
d
]
f[s][u][d]
f[s][u][d] s表示当前已联通的点集，u表示当前点集生成树的树根，d表示u到起点的距离，这里用记忆化搜索实现
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,w[13][13],f[1<<13][13][13];
inline int read(){
int X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
int dp(int s,int u,int d){
if(f[s][u][d]!=-1)return f[s][u][d];
if(s==(1<<(u-1)))return f[s][u][d]=0;
int& ans=f[s][u][d]=inf;
for(register int s1=s;s1;s1=(s1-1)&s){
if(!(s1&(1<<(u-1))))continue;
for(register int v=1;v<=n;v++){
if(!(s&(1<<(v-1))))continue;
if(w[u][v]==inf)continue;
int s2=s^s1;
ans=min(ans,dp(s1,u,d)+dp(s2,v,d+1)+w[u][v]*d);
}
}
return ans;
}
int main(){
n=read();m=read(); memset(w,inf,sizeof(w));
for(register int i=1,u,v,val;i<=m;i++){
u=read();v=read();val=read();
w[u][v]=w[v][u]=min(w[u][v],val);
}
int ans=inf;memset(f,-1,sizeof(f));
for(register int i=1;i<=n;i++)ans=min(ans,dp((1<<n)-1,i,1));
printf("%d\n",ans);
return 0;
}
|