线性 dp
线性 dp，就是指 dp 只有一维的 dp。因此，线性 dp 容易由 $\operatorname{O}(n)$ 的式子推出来。有时候，线性 dp 是需要结合其他的方法优化或者证明的。
例题
这一道题目可以很明显地推出式子，设 $dp_i$ 为以 $i$ 结尾的子序列最大长度。
$$\Large dp_i=\max_{j=1}^{i-1}(dp_j[a_i\ge a_j]+1)$$
那么，接下来，求出：
$$\Large\max_{i=1}^{n}(dp_i)$$
即可。
#include<bits/stdc++.h>
#define MAXN 5005
using namespace std;
int n,ans,a[MAXN],dp[MAXN];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
dp[n]=1;
for(int i=n-1;i>=1;--i){
int ans=0;
for(int j=i+1;j<=n;++j){
if(a[i]<=a[j]&&ans<dp[j]){
ans=dp[j];
}
}
dp[i]=1+ans;
}
for(int i=1;i<=n;++i){
if(ans<dp[i]){
ans=dp[i];
}
}
printf("%d",ans);
return 0;
}
背包 dp
01 背包
01 背包的题型是每一个物品都有价值 $w_i$ 和容量 $v_i$，你有一个总容量 $V$，你要从中选出若干个物品使得能够都装进背包然后价值总和最大。
很容易得出，将 $dp_{i,j}$ 表示为选到第 $i$ 个物品，剩余容量为 $j$ 的最大价值。且可以得出：
$$\Large dp_{i,j}=\max_{k=1}^{i-1}(dp_{k,j-v_{i}+w_{i}})$$
如果每一个 $dp_{i,j}$ 都继承上一个 $dp_{i-1,j}$，那么发现每一个 $i$ 都可以化成 $i$ 和 $i-1$ 的情况，所以可以用 $dp_{2,V}$ 来滚。
例题
01 背包板子题。
#include<bits/stdc++.h>
#define MAXN 101
#define MAXM 1001
using namespace std;
int w[MAXN],v[MAXN],dp[MAXM];
int main(){
int m,n;
scanf("%d %d",&m,&n);
for(int i=1;i<=n;++i){
scanf("%d %d",&w[i],&v[i]);
}
for(int i=1;i<=n;++i){
for(int j=m;j>=0;--j){
if(j>=w[i]){
dp[j]=max(dp[j-w[i]]+v[i],dp[j]);
}
}
}
printf("%d",dp[m]);
return 0;
}
多重背包
多重背包是指每一个物品都能够选择若干次的背包。有时候，可以暴力拆成若干个 01 背包，但是有时候空间和时间都不支持。所以，我们需要优化。
二进制分组优化
这个是利用任何一个数都能够拆成 $\sum2_{s_i}$ 的形式。可以把个数 $c_i$ 拆成 $1,2,4\dots$ 的形式，这样就能拼凑出所有方案。
单调队列优化
朴素的转移方程是：
$$\Large dp_{i,j}=\max_{k=0}^{c_i}(dp_{i-1,j-k\times v_i}+k\times w_i)$$
我们掏出一个 $G_{x,y}=dp_{i,x\times v_i+y}$，一个 $H_{x,y}=dp_{i-1,x\times v_i+y}$，$x$ 表示选多少个，$y$ 表示剩余容量，则有：
$$\Large G_{x,y}=\max_{k=0}^{c_i}(H_{x-k,y}+k\times w_i)$$
我们再掏出一个 $S_{x,y}=H_{x,y}-x\times w_i$，则有：
$$\Large G_{x,y}=\max_{k=0}^{c_i}(S_{x-k,y})+x\times w_i$$
很明显可以使用单调队列进行维护。
例题
套用单调队列优化背包模板。
#include<bits/stdc++.h>
#define MAXN 40004
using namespace std;
int dp[MAXN];
int main(){
int n,m,ans=0;
scanf("%d %d",&n,&m);
while(n--){
int w,v,sum;
scanf("%d %d %d",&v,&w,&sum);
if(!w){
ans+=v*sum;
continue;
}
sum=min(sum,m/w);
for(int i=0;i<w;++i){
deque<pair<int,int> > q;
int part=(m-i)/w;
for(int j=0;j<=part;++j){
while(!q.empty()&&dp[i+j*w]-j*v>=q.back().second){
q.pop_back();
}
q.push_back(make_pair(j,dp[i+j*w]-j*v));
while(!q.empty()&&q.front().first<j-sum){
q.pop_front();
}
dp[i+j*w]=max(dp[i+j*w],q.front().second+j*v);
}
}
}
printf("%d",ans+dp[m]);
return 0;
}
无限背包
无限背包是指各种背包都有无限个，很明显可以有暴力式子：
$$\Large dp_{i,j}=\max_{k=0}^{i-1}(dp_{k,j-v_i\times k}+w_i\times k)$$
但是，可以发现，$dp_{i,j}$ 只需要通过 $dp_{i-1,j-v_i}$ 来转移即可。所以，基本上变成了 01 背包的代码。同样可以优化掉一维来优化。
例题
套用无限背包板子。
#include<bits/stdc++.h>
#define MAXN 10001
#define MAXM 10000001
using namespace std;
typedef long long ll;
ll v[MAXN],w[MAXN],dp[MAXM];
int main(){
int m,n;
scanf("%d %d",&m,&n);
for(int i=1;i<=n;++i){
scanf("%lld %lld",&w[i],&v[i]);
}
for(int i=1;i<=n;++i){
for(int j=w[i];j<=m;++j){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
printf("%lld",dp[m]);
return 0;
}
混合背包
混合背包是指有一些物品能够拿 $1$ 次，有些物品能够拿 $c_i$ 次，有些物品能够拿无限次。这种背包只需要分类讨论每一种背包即可。
例题
套用混合背包板子。
#include<bits/stdc++.h>
#define MAXN 10001
#define MAXM 1001
using namespace std;
typedef long long ll;
int w[MAXN],v[MAXN],cnt[MAXN];
ll dp[MAXM];
inline ll time(){
ll sh,ss,eh,es;
scanf("%lld:%lld %lld:%lld",&sh,&ss,&eh,&es);
ll s=sh*60+ss,e=eh*60+es;
return e-s;
}
int main(){
int m=time(),n;
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d %d %d",&v[i],&w[i],&cnt[i]);
}
for(int i=1;i<=n;++i){
if(!cnt[i]){
for(int j=v[i];j<=m;++j){
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}else{
for(int j=1;j<=cnt[i];++j){
for(int k=m;k>=j*v[i];--k){
dp[k]=max(dp[k],dp[k-v[i]]+w[i]);
}
}
}
}
printf("%lld",dp[m]);
return 0;
}
区间 dp
区间 dp 是指在 $dp_{l,r}$ 形式的 dp。这种 dp 是通过子区间来进行合并转移的，即 $dp_{l,r}=merge(dp_{l,k},dp_{k+1,r})$。这种思想是基于分治的。比如要想得到 $dp_{1,4}$，就得先得到 $dp_{1,1}$ 和 $dp_{2,4}$、$dp_{1,2}$ 和 $dp_{3,4}$ 或者 $dp_{1,3}$ 和 $dp_{4,4}$。
例题
记 $dp_{l,r}$ 为合并 $[l,r]$ 的最大值，然后可以套用 dp 公式。
#include<bits/stdc++.h>
#define MAXN 202
using namespace std;
int a[MAXN],dp[MAXN][MAXN];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
a[i+n]=a[i];
}
for(int len=2;len<=2*n;++len){
for(int l=1,r=len;r<=2*n;++l,++r){
for(int k=l;k<r;++k){
dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+a[l]*a[r+1]*a[k+1]);
}
}
}
int ans=0;
for(int i=1;i<=2*n;++i){
ans=max(ans,dp[i][i+n-1]);
}
printf("%d",ans);
return 0;
}
树形 dp
树形 dp 是通过树的顺序或者图的拓扑序来进行的 dp。通常来讲，子节点继承父节点的状态或者父节点继承诸多子节点的状态。
例题
很明显，看到这一条保证：
如果有一个编号为 $A$ 机器人指控或保护编号为 $B$ 的机器人，那么我们保证 $A<B$。
就可以推出这一个关系是一棵树。这时候，我们就可以使用树形 dp 来解。
很明显，当一条指控边出现，只可能是：
- 狼人指控村民。
- 村民指控狼人。
- 村民指控村民。
当一条保护边出现，只可能是：
- 狼人保护狼人。
- 村民保护狼人。
- 村民保护村民。
所以，利用这两点来建边就可以进行 dp 了。
具体可以使用记忆化搜索来实现。由于可能有森林的出现，所以定义一个根节点 $0$ 来连接其他点。从 $0$ 开始搜索，向下搜索，设 $dp_{i,j,k}(1\le i\le n,1\le j\le m,k\in{0,1})$ 为当前是节点 $i$，前面出现了 $j$ 个狼人，当前节点是否为狼人的方案数。
接下来，设 $u,v$ 表示 $u$ 有一条边通向 $v$，那么分类讨论：
- 如果要计算为狼人的情况，并且为指控边，那么子节点必须为村民，则有 $dp_{u,j,1}=dp_{u,j-k,1}\times dp_{v,k,0}$。
- 如果要计算为狼人的情况，并且为保护边，那么子节点必须为狼人，则有 $dp_{u,j,1}=dp_{u,j-k,1}\times dp_{v,k,1}$。
- 如果要计算为村民的情况，并且为指控边，那么子节点可以为村民和狼人，需要加和，有 $dp_{u,j,0}=dp_{u,j-k,0}\times(dp_{v,k,0}+dp_{v,k,1})$。
- 如果要计算为村民的情况，并且为保护边，那么子节点可以为村民和狼人，需要加和，有 $dp_{u,j,0}=dp_{u,j-k,0}\times(dp_{v,k,0}+dp_{v,k,1})$。
#include<bits/stdc++.h>
#define MAXN 202
#define MAXM 40004
#define MOD 1000000007
using namespace std;
typedef long long ll;
struct node{
int next,to;
bool type;
}edge[MAXM<<2];
int n,m,k,cnt,head[MAXN];
bool vis[MAXN];
inline void addedge(int from,int to,bool type){
edge[++cnt].to=to;
edge[cnt].type=type;
edge[cnt].next=head[from];
head[from]=cnt;
}
ll dp[MAXN][MAXN][2];
int size[MAXN];
bool in[MAXN];
void dfs(int u){
size[u]=1;
dp[u][0][0]=dp[u][1][1]=1ll;
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].to;
dfs(v);
size[u]+=size[v];
for(int j=size[u];j>=0;--j){
ll ans1=0,ans0=0;
for(int k=min(j,size[v]);k>=0;--k){
if(edge[i].type){
(ans1+=dp[u][j-k][1]*dp[v][k][0])%=MOD;
}else{
(ans1+=dp[u][j-k][1]*dp[v][k][1])%=MOD;
}
(ans0+=dp[u][j-k][0]*(dp[v][k][0]+dp[v][k][1]))%=MOD;
}
dp[u][j][0]=ans0;
dp[u][j][1]=ans1;
}
}
}
int main(){
scanf("%d %d %d",&n,&m,&k);
while(k--){
int u,v;
char s[3]="";
scanf("%s %d %d",s,&u,&v);
if(*s=='A'){
addedge(u,v,true);
}else{
addedge(u,v,false);
}
in[v]=true;
}
for(int i=1;i<=n;++i){
if(!in[i]){
addedge(0,i,true);
}
}
dfs(0);
printf("%lld",dp[0][m][0]);
return 0;
}
状压 dp
状压 dp，就是把一些维度压缩成一个维度的 dp。比如，你需要记录 $1$ 到 $10$ 之内的布尔值，那么可以把 $10$ 位压缩成一个 int，也就是 $2^{10}$ 的空间。
有一些状压的基本操作：
(zip>>i)&1表示查询 $zip$ 单位里面的第 $i$ 个元素的布尔值。zip|(1<<(i-1))表示在 $zip$ 的基础上将第 $i$ 个元素值修改成 $1$。zip-(1<<(i-1))表示在 $zip$ 的第 $i$ 的位置上是 $1$ 的基础上将 $i$ 修改成 $0$。__builtin_popcount(zip)表示统计 $zip$ 中有多少个 $1$。
状态压缩通常用于优化数位 dp。
例题
设 $dp_{zip,i}$ 表示走过的状态为 $zip$，下一个要走第 $i$ 个的状态。枚举每一个 $j$ 转移过来。如果 $zip$ 里面出现过 $j$，那就更新答案。
#include<bits/stdc++.h>
#define MAXN 21
using namespace std;
int n,dis[MAXN][MAXN],dp[1<<20|1][MAXN];
inline int read(){
int res=0;
char c=getchar();
while(!isdigit(c)){
c=getchar();
}
while(isdigit(c)){
res=(res<<1)+(res<<3)+(c^48);
c=getchar();
}
return res;
}
inline void write(int x){
if(x>9){
write(x/10);
}
putchar(x%10+'0');
}
int main(){
n=read();
for(register int i=1;i<=n;++i){
for(register int j=1;j<=n;++j){
dis[i][j]=read();
}
}
memset(dp,0x3f,sizeof(dp));
dp[1][1]=0;
for(register int zip=1;zip<(1<<n);++zip){
for(register int i=1;i<=n;++i){
if(zip&(1<<(i-1))){
continue;
}
for(register int j=1;j<=n;++j){
if(!(zip&(1<<(j-1)))){
continue;
}
dp[zip|(1<<(i-1))][i]=min(dp[zip|(1<<(i-1))][i],dp[zip][j]+dis[j][i]);
}
}
}
int ans=INT_MAX;
for(register int i=2;i<=n;++i){
ans=min(ans,dp[(1<<n)-1][i]+dis[i][1]);
}
write(ans);
return 0;
}
优化
单调队列优化
在背包 dp 里面有提到过。原理是将 $dp$ 式子化成形如 $\max_{i=0}^{n}(dp)$ 类型的式子。
例题
很明显，初始 dp 式子是 $dp_{t,i,j}=\max(dp_{t-1,i,j},dp_{t-1,pre(i),pre(j)})$。其中，$pre$ 函数是该位置的上一个位置。在同一个方向上，可以使用单调队列优化。
#include<bits/stdc++.h>
#define MAXN 210
using namespace std;
int n,m,x,y,k,ans;
int dx[5]={0,-1,1,0,0};
int dy[5]={0,0,0,-1,1};
int dp[MAXN][MAXN];
char mp[MAXN][MAXN];
inline void move(int x,int y,int p,int l,int r){
deque<pair<int,int> > q;
for(int i=1;1<=x&&x<=n&&1<=y&&y<=m;++i,x+=dx[p],y+=dy[p]){
if(mp[x][y]=='x'){
q.clear();
}else{
while(!q.empty()&&q.back().first+i-q.back().second<dp[x][y]){
q.pop_back();
}
q.push_back(make_pair(dp[x][y],i));
while(!q.empty()&&q.back().second-q.front().second>r-l+1){
q.pop_front();
}
ans=max(ans,dp[x][y]=q.front().first+i-q.front().second);
}
}
}
int main(){
scanf("%d %d %d %d %d",&n,&m,&x,&y,&k);
for(int i=1;i<=n;++i){
scanf("%s",mp[i]+1);
}
memset(dp,0xf3,sizeof(dp));
dp[x][y]=0;
for(int i=1;i<=k;++i){
int l,r,face;
scanf("%d %d %d",&l,&r,&face);
if(face==1){
for(int j=1;j<=m;++j){
move(n,j,face,l,r);
}
}else if(face==2){
for(int j=1;j<=m;++j){
move(1,j,face,l,r);
}
}else if(face==3){
for(int j=1;j<=n;++j){
move(j,m,face,l,r);
}
}else if(face==4){
for(int j=1;j<=n;++j){
move(j,1,face,l,r);
}
}
}
printf("%d",ans);
return 0;
}
矩阵快速幂
矩阵快速幂是用于优化 dp 的。它通常能够优化到 $\log$ 级别的递推。
矩阵快速幂的本质是利用矩阵乘法的乘法结合律来用 $\log n$ 的时间复杂度来求出分矩阵，然后乘上原矩阵。
矩阵乘法的规则如下：
- 定义 $x$ 为长度 $n,m$ 的矩阵，$y$ 为长度 $m,k$ 的矩阵，那么它们相乘的结果为长度为 $n,k$ 的矩阵 $res$。
- $res_{i,j}=\sum_{k=1}^{m}x_{i,k}\times y_{k,j}$。
可以看出这一个式子似乎能够优化所有转移方程只带加法和乘法的 dp。但是，要证明两点：
- 矩阵乘法不满足乘法交换律，因为交换后 $n$ 可能不等于 $k$。
- 矩阵乘法满足结合律。因为 ${n,m}\times{m,k}\times{k,l}$，不管先算哪一个，要么得出 ${n,k}\times{k,l}={n,l}$，要么得出 ${n,m}\times{m,l}={n,l}$。
所以，矩阵乘法满足结合律。那么，矩阵乘法的递推式要视情况而定。
例题
这一道题目可以推出 dp 式子，设 $dp_{i,k}(1\le i\le n,k\in{0,1})$ 表示表示所有以 $i$ 为结尾的子串，选择相应的 $b$，满足 $k$ 对于相应子串是忠诚的，且 $k$ 的结尾与相应子串相同和不同的概率和。
设 $dp_{i,0/1}$ 表示所有以 $i$ 结尾的且长度在 $l$ 到 $r$ 之间的字串，选择相应的 $j$，满足 $j$ 对于相应字串是忠诚的，且 $j$ 的结尾相应字串相同和不同的概率和。另外设置辅助 dp 数组 $ldp_{i,0/1}$，$rdp_{i,0/1}$ 表示 $dp$ 数组，不同的是长度分别为 $1$ 到 $l-1$ 和 $r+1$ 到 $n$。递推式：
$$\Large dp_{i,0}=\frac{1}{2}\times(dp_{i-1,0}+dp_{i-1,1})+\frac{ldp_{i,0}}{2l}-\frac{rdp_{i,0}}{2r}$$
设 $g_{i,0/1}$ 表示到第 $i$ 个位置有多少个字串 $j$ 是忠诚的，有递推式 $g_{i,0}=g_{i-1,0}+g_{i-1,1}$，$g_{i,1}=g_{i-1,a_i}$。那么这一部分可以使用矩阵快速幂优化。之后，可以利用 $g$ 来求出 $ldp$ 和 $rdp$。
#include<bits/stdc++.h>
#define MOD 998244353
#define MAXN 5000005
#define getchar getchar_unlocked
#define putchar putchar_unlocked
using namespace std;
typedef long long ll;
typedef vector<vector<ll> > matrix;
matrix mtr1[2],mtr2[2],mtr3;
int n,l,r;
ll res1,res2,invl,invr,ans[MAXN],ldp[2][MAXN],rdp[2][MAXN],dp[2][MAXN];
inline ll read(void){
ll res=0;
char c=getchar();
while(!isdigit(c)){
c=getchar();
}
while(isdigit(c)){
res=(res<<1)+(res<<3)+(c^'0');
c=getchar();
}
return res;
}
void write(ll res){
if(res>9){
write(res/10);
}
putchar(res%10+'0');
}
inline matrix multi(const matrix &mtr1,const matrix &mtr2){
matrix res;
res.resize(2);
res[0].resize(2);
res[1].resize(2);
res[0][0]=(mtr1[0][0]*mtr2[0][0]+mtr1[0][1]*mtr2[1][0])%MOD;
res[1][0]=(mtr1[1][0]*mtr2[0][0]+mtr1[1][1]*mtr2[1][0])%MOD;
res[0][1]=(mtr1[0][0]*mtr2[0][1]+mtr1[0][1]*mtr2[1][1])%MOD;
res[1][1]=(mtr1[1][0]*mtr2[0][1]+mtr1[1][1]*mtr2[1][1])%MOD;
return res;
}
inline ll power(ll x,ll y){
ll res=1;
while(y){
if(y&1){
(res*=x)%=MOD;
};
(x*=x)%=MOD;
y>>=1;
}
return res;
}
inline ll inv(int number){
return power(number,MOD-2);
}
const static ll invof2=inv(2);
int main(){
mtr1[0].resize(2);
mtr1[1].resize(2);
mtr2[0].resize(2);
mtr2[1].resize(2);
for(register int i=0;i<2;++i){
mtr1[0][i].resize(2);
mtr1[1][i].resize(2);
mtr2[0][i].resize(2);
mtr2[1][i].resize(2);
}
mtr1[0][0][0]=mtr1[0][0][1]=mtr1[0][1][0]=1;
mtr2[0][0][1]=mtr2[0][1][0]=1;
mtr1[1][0][0]=mtr1[1][1][0]=mtr1[1][1][1]=1;
mtr2[1][0][0]=mtr2[1][1][1]=1;
mtr2[0][1][1]=mtr2[1][1][0]=MOD-1;
n=read();
l=read();
r=read();
invl=inv(power(2,l));
invr=inv(power(2,r+1));
res2=inv((1ll*(n*2-l-r+2)*(r-l+1)/2)%MOD);
for(register int i=1;i<=n;++i){
char c=getchar();
while(c!='1'&&c!='0'){
c=getchar();
}
ans[i]=c-'0';
}
mtr3.resize(2);
mtr3[0].resize(2);
mtr3[1].resize(2);
mtr3[0][0]=mtr3[1][1]=1;
mtr3[0][1]=mtr3[1][0]=0;
for(register int i=1;i<l;++i){
mtr3=multi(mtr3,mtr1[ans[i]]);
}
for(register int i=l;i<=n;++i){
mtr3=multi(multi(mtr2[ans[i-l+1]],mtr3),mtr1[ans[i]]);
ldp[0][i]=(mtr3[0][0]+mtr3[1][0])%MOD;
ldp[1][i]=(mtr3[0][1]+mtr3[1][1])%MOD;
}
mtr3[0][0]=mtr3[1][1]=1;
mtr3[0][1]=mtr3[1][0]=0;
for(register int i=1;i<=r;++i){
mtr3=multi(mtr3,mtr1[ans[i]]);
}
for(register int i=r+1;i<=n;++i){
mtr3=multi(multi(mtr2[ans[i-r]],mtr3),mtr1[ans[i]]);
rdp[0][i]=(mtr3[0][0]+mtr3[1][0])%MOD;
rdp[1][i]=(mtr3[0][1]+mtr3[1][1])%MOD;
}
for(register int i=1;i<=n;++i){
(dp[0][i]=(invof2*(dp[0][i-1]+dp[1][i-1])+invl*ldp[0][i]-invr*rdp[0][i])%MOD+MOD)%=MOD;
(dp[1][i]=(invof2*(dp[ans[i]][i-1])+invl*ldp[1][i]-invr*rdp[1][i])%MOD+MOD)%=MOD;
(res1+=(dp[0][i]+dp[1][i])%MOD)%=MOD;
}
write((res1*res2%MOD+MOD)%MOD);
return 0;
}