DP 入门

Arahc 11.0
  2022-06-21 08:00 2022-06-21 08:00 创建   2023-03-16 13:55:34 2023-03-16 13:55:34 更新      8.4k 字  40 分钟  

这些天搞了搞 DP 专题，把一些动态规划的东西总结一下。

PS：在原本的博客站里我分成了两个文章，现在决定把它们合并。

状态设计

DP+DP

考虑一个问题，如果不能简单地用一个 DP 去解决，我们可以再来一个。

当然还有的 DP+DP 的目的是平衡复杂度，在后面会有的。

Luogu3188 梦幻岛宝珠

给定 nn 个物品，每个物品有重量和价值。一个物品只能选一次，求限重 mm 的情况下，能装载的物品价值和的最大值。

n≤100,m≤231n\leq100,m\leq 2^{31}，每个重量能写成 a×2b(a≤10,b≤30)a\times 2^b(a\leq10,b\leq30) 的形式。

题解

考虑 nn 的值很小。

对 bb 相同的物品可以跑朴素的 01 背包，求 fi,jf_{i,j} 表示 b=ib=i，容量为 jj 的最大价值。

然后考虑合并答案。设 gi,jg_{i,j} 表示当前考虑到 b=ib=i，且 b=ib=i 的物品占用空间为 jj 时，b∈[0,i)b\in[0,i) 的部分空间不超过容量第 ii 位的最大价值。

转移考虑从 jj 里面拆掉一个 kk 给其他物品放：

gi,j←max⁡(gi,j,fi,j−k+gi−1,min⁡(10n,2k+(m>>(i−1))&1))g_{i,j} \gets \max(g_{i,j} , f_{i,j-k} + g_{i-1,\min(10n,2k+(m>>(i-1))\&1)})

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for(register int i=1;i<=n;++i){
    int x=read(),cnt=x&-x;
    int id=getbitnum(cnt);
    w[id][++num[id]]=x/cnt;
    v[id][num[id]]=read();
}
int up=get(W);
for(register int i=0;i<=up;++i)
    for(register int j=1;j<=num[i];++j)
        for(register int k=500;k>=w[i][j];--k)
            dp[i][k]=max(dp[i][k],dp[i][k-w[i][j]]+1LL*v[i][j]);
for(register int i=0;i<=500;++i)
    f[0][i]=dp[0][i];
for(register int i=1,nw=1;i<=up;++i,nw^=1)
    for(register int j=0;j<=500;++j){
        f[nw][j]=0;
        for(register int k=0;k<=j;++k){
            f[nw][j]=max(f[nw][j],
            dp[i][j-k]+f[nw^1][min(10*n,(k<<1)+((W>>(i-1))&1))]);
        }
    }

容斥原理

用容斥进行的 DP 不少了，还是一句话，正难则反。

基本上有两大类：

  • 直接转化为全集-补集，用 DP 求解补集问题。
  • 以常规的容斥原理进行 DP，或用二项式定理、容斥原理等合并 DP 的答案。

通常我们建立的求的东西和答案所需的东西为二项式反演的关系，组合数学里有时是斯特林反演的关系，毒瘤出题人可能会把它放在计算几何里形成圆反演的关系。

上一个经典问题：

Luogu4859 已经没有什么好害怕的了

给定两个序列 a,ba,b，两序列无重复元素，无交。求将两个序列两两配对，使得 ai>bja_i>b_j 的组数比 ai<bja_i<b_j 的组数恰好多 KK 的配对方案数。

n≤2000n\leq 2000。

题解

令 K←n+K2K\gets \frac{n+K}{2}，则我们只需要让 ai>bja_i > b_j 的组数为 KK 即可。先将两个数组排序。

若一个 aia_i 匹配到了比它小的 bjb_j，则对于任意 j>ij>i，它匹配比它小的 bkb_k 的方案数会 −1-1。

这种情况貌似还算好考虑：设计状态 fi,jf_{i,j} 表示考虑到第 ii 位，已经产生了 jj 个上述情况的方案数，设 cic_i 表示 bb 序列里比 aia_i 小的数有多少个，有：

fi,j=fi−1,j+(ci−j+1)fi−1,j−1f_{i,j} = f_{i-1,j}+ (c_i-j+1) f_{i-1,j-1}

剩下的数字是不是任意匹配？那如何得到恰好 KK 组的答案？这是不好算的，但是至少 KK 组的答案呢？

设 gig_i 表示将 n−in-i 个没有按上述方法匹配的数任意分配，得到至少 ii 组合法匹配的方案数。不难有 gi=(n−i)!fn,ig_i = (n-i)!f_{n,i}。

然后容斥答案即可：

ans=∑i=Kn(−1)i−K(iK)gians = \sum_{i=K}^n (-1)^{i-K} \binom{i}{K} g_i

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(register int i=1;i<=n;++i)
    for(register int j=0;j<=i;++j){
        dp[i][j]=dp[i-1][j];
        if(j && l[i]-j+1>0){
            dp[i][j]+=(l[i]-j+1)*dp[i-1][j-1]%mod,
            dp[i][j]%=mod;
        }
    }
for(register int i=0;i<=n;++i)
    f[i]=dp[n][i]*fac[n-i]%mod;
for(register int i=k;i<=n;++i){
    ans+=((i-k)&1?-1:1)*C(i,k)*f[i]%mod,
    ans=(ans+mod)%mod;
}

DP of DP

这是一个神奇的思想。

设计动态规划的时候，从另外一个动态规划入手，考虑另外一个动态规划的转移，挖掘性质，然后建立一个动态规划来维护这个动态规划的转移。

有时候还需要我们会建一个自动机，然后在自动机上跑 DP。

BZOJ3864 Hero meet devil

给定一个由 AGCT 组成的字符串 SS，对于每个 0≤i≤∣S∣0\leq i\leq \left|S\right|，求有多少个长度为 mm 的字符串 TT，满足 S,TS,T 的最长公共子序列为 ii。

∣S∣≤15,m≤1000\left|S\right|\leq15,m\leq 1000。

题解

考虑如何求两个字符串的 LCS，这是一个非常经典的 DP：设 dpi,jdp_{i,j} 表示考虑到 Si,TjS_i,T_j，最长公共子序列的长度：

dpi,j=max⁡{dpi−1,j−1+1(Si=Ti)dpi,j−1dpi−1,jdp_{i,j} = \max\begin{cases}dp_{i-1,j-1} +1 & (S_i = T_i) \\dp_{i,j-1} \\dp_{i-1,j}\end{cases}

考虑这个 DP 有什么特殊性质，我们发现 dpi,j−dpi,j−1∈{0,1}dp_{i,j}-dp_{i,j-1} \in \{0,1\}。

对 dpidp_i 差分，用差分数组当状态。设 fi,sf_{i,s} 表示长度为 ii 的字符串与 SS 的 LCS 的 DP 匹配状态为 ss 的方案数。

实际转移前需要预处理出每个状态添加一个字符能转移到哪些状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
for(register int i=0;i<S;++i){
    for(register int j=1;j<=n;++j)
        f[j]=f[j-1]+((i>>(j-1))&1);
    for(register int k=0;k<4;++k){
        for(register int j=1;j<=n;++j){
            g[j]=max(g[j-1],f[j]);
            if(k==s[j])
                g[j]=max(g[j],f[j-1]+1);
        }
        to[i][k]=0;
        for(register int j=1;j<=n;++j)
            if(g[j]-g[j-1])
                to[i][k]|=(1<<(j-1));
    }
}
memset(dp,0,sizeof(dp)),
memset(ans,0,sizeof(ans));
dp[0][0]=1;
for(register int i=1,nw=1;i<=m;++i,nw^=1){
    memset(dp[nw],0,sizeof(dp[nw]));
    for(register int st=0;st<S;++st)
        for(register int j=0;j<4;++j)
            dp[nw][to[st][j]]=(dp[nw][to[st][j]]+dp[nw^1][st])%mod;
}

状态数优化

顾名思义，就是挖掘题目的性质，考虑如何优化状态数。

状态数优化还有一种精妙的实现方式：如果原 DP 的一维值域很大，但是 DP 值很小，考虑交换 DP 维度和答案。也可以实现状态数的优化。

当然更多的状态数优化还是如下几种：

  1. 从根本上优化：去除一个或几个维度。
  2. 挖掘性质，去除冗余状态。
  3. 离散、压缩、合并状态。

CF643E Bear and Destroying Subtrees

一个树，初始只有根。支持添加叶子或查询如下问题的答案：

每条边若有 50%50\% 的概率断裂，则断边后点 xx 的子树的期望高度。

误差不超过 10−610^{-6}，Q≤5×105Q\leq 5\times 10^5。

题解

考虑朴素 DP 有：fi,jf_{i,j} 表示 ii 为根的子树内，断边后深度为 jj 的概率。转移是 naive 的。每次加入一个叶子的时候，需要从这个叶子一直跳到根，更新这条链上所有点的状态。更新状态是 O(1)\mathcal O(1) 的。

转移复杂度非常优秀，考虑如何优化状态。注意到精度要求为 10−610^{-6}，因此对于一个树，断边后高度的期望值其实不大。

例如如果断边后高度达到 100100，即使有 5×1055\times 10^5 个点，概率也只有 10−3110^{-31}，对答案几乎没有影响。这些状态几乎是冗余的。

因此状态的第二维可以开得比较小，每次加入叶子往上也不需要跳到根，跳到某一级祖先就够了。

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
57
58
59
60
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool Begin;
const int max_n=500005;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}

int n=1,fa[max_n];
const int D=100;

double f[max_n][D+5];

inline void dfs1(int u,int i){
    if(!fa[u] || i>=D) return;
    dfs1(fa[u],i+1);
    f[fa[u]][i+1]/=(f[u][i]+1)/2.0;
}
inline void dfs2(int u,int i){
    if(!fa[u] || i>=D) return;
    f[fa[u]][i+1]*=(f[u][i]+1)/2.0;
    dfs2(fa[u],i+1);
}

bool End;
#define File ""
signed main(){
    // #ifndef ONLINE_JUDGE
    // freopen(File ".in","r",stdin);
    // freopen(File ".out","w",stdout);
    // #endif
    // cerr<<"Memory : "<<(&Begin-&End)/1024.0/1024<<"\n";
    for(register int i=1;i<=D;++i)
        f[1][i]=1;
    for(register int Q=read();Q;--Q){
        int tp=read(),x=read();
        if(tp==1){
            fa[++n]=x;
            for(register int i=1;i<=D;++i)
                f[n][i]=1;
            dfs1(x,1),dfs2(n,0);
        }
        else{
            double ans=D;
            for(register int i=1;i<D;++i)
                ans-=f[x][i];
            printf("%.10lf\n",ans-1);
        }
    }
    return 0;
}

HDU4623 Crime

求有多少大小为 nn 的排列满足相邻两个数互质。

n≤28n\leq 28。

题解

暴力 DP 设 fi,sf_{i,s} 表示最后一个数填的是 ii，已经填了集合 ss 中的数，状态数为 228×282^{28}\times 28。太大了。不能通过。

注意到我们并不需要知道这个数具体是什么，只需要让其和上一个数不互质即可。

对每个数按照其有的质因子分类，注意到 1,17,19,231,17,19,23 和任何数都互质，可以单独划分到一类。

然后你就有了 1414 类数，预处理每一类数的互质情况，设 fi,sf_{i,s} 表示最后一个数是 ii 类，每个类剩余数字情况为 ss 的方案数，则状态数为 14×172800014\times 1728000，可以通过。

这题最好写变进制状压，不要学我暴力压然后写了个高达十几维的 DP。

1
2
3
4
5
6
7
8
9
10
11
12
13
for(register int i=0;i<14;++i)
    f[i==0][i==1][i==2][i==3][i==4][i==5][i==6][i==7][i==8][i==9][i==10][i==11][i==12][i==13][i]=1;
for(I[0]=0;I[0]<=up[0];++I[0]) for(I[1]=0;I[1]<=up[1];++I[1]) for(I[2]=0;I[2]<=up[2];++I[2]) for(I[3]=0;I[3]<=up[3];++I[3])
for(I[4]=0;I[4]<=up[4];++I[4]) for(I[5]=0;I[5]<=up[5];++I[5]) for(I[6]=0;I[6]<=up[6];++I[6]) for(I[7]=0;I[7]<=up[7];++I[7])
for(I[8]=0;I[8]<=up[8];++I[8]) for(I[9]=0;I[9]<=up[9];++I[9]) for(I[10]=0;I[10]<=up[10];++I[10]) for(I[11]=0;I[11]<=up[11];++I[11])
for(I[12]=0;I[12]<=up[12];++I[12]) for(I[13]=0;I[13]<=up[13];++I[13]) for(register int i=0;i<14;++i) if(I[i])
    for(register int j=0;j<14;++j) if(!conf[i][j] && I[j]<up[j]){
        int &to=f[I[0]+(j==0)][I[1]+(j==1)][I[2]+(j==2)][I[3]+(j==3)][I[4]+(j==4)][I[5]+(j==5)][I[6]+(j==6)][I[7]+(j==7)][I[8]+(j==8)][I[9]+(j==9)][I[10]+(j==10)][I[11]+(j==11)][I[12]+(j==12)][I[13]+(j==13)][j];
        to=(to+f[I[0]][I[1]][I[2]][I[3]][I[4]][I[5]][I[6]][I[7]][I[8]][I[9]][I[10]][I[11]][I[12]][I[13]][i])%mod;
    }
int ans=0;
for(register int i=0;i<14;++i)
    ans=(ans+f[up[0]][up[1]][up[2]][up[3]][up[4]][up[5]][up[6]][up[7]][up[8]][up[9]][up[10]][up[11]][up[12]][up[13]][i])%mod;

转移优化

所谓转移优化，你先得要有一个暴力的转移。

然后根据观察方程/打表找性质等方法选择合适的优化。如果优化不了，反思一下是不是有更好的状态设计。

决策单调性

决策单调性，顾名思义，就是在转移过程中，使 dp 数组有最优转移的下标具有某些性质（一般是单调性），从而可以用此优化 DP。

通常证明一个决策单调性非常复杂，而且一般你也想不到这个题有决策单调性。因此考场上常用的找决策单调性的做法为打表观察。

设 ff 为状态数组，pp 为最优转移的决策，常见的决策单调性有两种：

  1. pp 单调。
  2. 四边形不等式。

若 a1≤a2<b1≤b2,fa1,b1+fa2,b2≤fa1,b2+fa2,b1a_1 \leq a_2 < b_1 \leq b_2, f_{a_1,b_1}+f_{a_2,b_2} \leq f_{a_1,b_2}+f_{a_2,b_1}，则 ff 满足四边形不等式。

若 ff 满足四边形不等式，则 pi,j−1≤pi,j≤pi+1,jp_{i,j-1}\leq p_{i,j}\leq p_{i+1,j}。

【数据删除】

给定两个 n×nn\times n 的网格图，横向边都是向右的。已知第一个图左侧第 ii 个点到右侧第 jj 个点的最短路 ai,ja_{i,j} 和第二个图左侧第 ii 个点到右侧第 jj 个点的最短路 bi,jb_{i,j}。

现在要把两个图拼成 n×2nn\times 2n 的网格图，求拼接后左侧第 ii 个点到右侧第 jj 个点的最短路 ci,jc_{i,j}。

n≤1000n\leq 1000。

题解

暴力 Floyd，ci,j=min⁡(ai,k+bk,j)c_{i,j} = \min(a_{i,k}+b_{k,j})，复杂度为三次方。题目说是网格图，但是图本身并没有给我们，所以边权之类的也找不到性质。

如果没什么思路的话，不妨先写出来，打个表观察决策吧？不难发现，设 pi,jp_{i,j} 表示使 ci,jc_{i,j} 最小的决策点，打表发现 pi,j≥pi,j−1p_{i,j}\geq p_{i,j-1}。为什么？

pic-1

  • len(x,P)=len(y,P)\rm{len}(x,P) = \rm{len}(y,P)，对答案无影响。
  • len(x,P)<len(y,P)\rm{len}(x,P) < \rm{len}(y,P)，BB 的最优决策在 xx。
  • len(x,P)>len(y,P)\rm{len}(x,P) > \rm{len}(y,P)，AA 的最优决策在 yy。

考虑每次转移的时候，假设要求出 fl⋯rf_{l\cdots r} 的值，且已经知道了 L≤pl≤pr≤RL\leq p_l\leq p_r\leq R，则直接二分出 midmid，求出 fmid,pmidf_{mid}, p_{mid}，求可以递归了。

复杂度 n2log⁡nn^2\log n。

斜率优化

可以大致分为两种：

  1. 转移方程写成向量点积的形式：fi=min⁡(Aj+BiCj+Di)f_i = \min(A_j + B_iC_j + D_i)。
  2. 转移方程可以转化为求最优斜率：fi=min⁡(Ai−BjCi−Dj)f_i = \min(\frac{A_i-B_j}{C_i-D_j})。

不同于决策单调性，判定一个 DP 是否可以斜率优化一般直接观察转移方程。

单调栈、单调队列、平衡树、分治……乱七八糟的东西都可以维护，但是因规约不同有些还不能用（比如点集的每一维都没有单调性时，不能用单调栈维护等等）。

【数据删除】

有 nn 个盒子，分别有 aia_i 个球，但球数和盒子无法一一对应。你可以每次选一个盒子拿一个球，如果这个盒子空了裁判会告诉你。求把 mm 个盒子取空的最坏情况下至少要拿多少球。

n≤2000,ai≤106n\leq 2000,a_i\leq 10^6。

题解

显然先排序。考虑最后空盒子的集合对应在 aa 上的下标为 {b1,b2,⋯ ,bm}\{b_1,b_2,\cdots,b_m\}，则最坏情况下球数为：

∑i=1mabi(bi−bi−1)\sum_{i=1}^m a_{b_i}(b_i - b_{i-1})

最优策略为：每个盒子模 ab1a_{b_1} 个球到空，剩下的盒子每个摸 ab2a_{b_2} 个球……

状态设计就简单了：fi,jf_{i,j} 表示考虑到第 ii 个盒子，空了 jj 个的最小球数：

fi,j=min⁡(fk,j−1+a1(i−k))f_{i,j} = \min(f_{k,j-1} + a_1(i-k))

这个式子可以化为斜率优化通式一。单调队列优化即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
inline double slp(int k1,int k2,int j){
    return 1.0*(f[k2][j]-f[k1][j])/(k2-k1);
}
// ...
for(register int i=1;i<=n;++i){
    for(register int j=i;j>0;--j){
        if(j==1)
            f[i][1]=i*a[i];
        else{
            while(q[j-1].size()>1 && slp(q[j-1][q[j-1].size()-2],q[j-1].back(),j-1)>=a[i])
                q[j-1].pop_back();
            f[i][j]=(i-q[j-1].back())*a[i]+f[q[j-1].back()][j-1];
        }
        while(q[j].size()>1 && slp(q[j][q[j].size()-2],q[j].back(),j)>=slp(q[j].back(),i,j))
            q[j].pop_back();
        q[j].push_back(i);
    }
    ans=min(ans,f[i][m]);
}

DS 优化

通常见到一个 DP，如果你看起来觉得它非常能 DS，那么它就可以 DS。

如果遇到一个题，它本身看起来像 DS，但它也可能是 DP+DS 优化。

有些东西看起来就不像是 DS 只像是有更优的状态/转移，它还是有可能是 DS 优化 DP。

CF1129D Isolation

给定序列 aa，将其划分为若干段，使得每段恰好出现一次的元素个数 ≤K\leq K，求方案数。

n≤105n\leq 10^5。

题解

这个暴力 DP 的思想就更简单了：

fi=∑j is okfjf_i = \sum_{\text{j is ok}} f_j

考虑怎么判 ok。记 gjg_j 为 (j,i](j,i] 这个区间内只出现一次的数的个数。所有可转移的 jj 就是满足 gj≤Kg_j\leq K 的 jj。而 gg 的维护：每次 ii 加一时相当于对 gg 进行区间加和区间减。

问题转化为：对 gg 区间 ±1\pm1，维护集合 S={i∣gi≤K}S = \{i|g_i\leq K \}。

考虑分块。给每个块开一个桶，整块修改打一个整体加减标记，局域修改暴力重构；整块查询直接查，局域查询暴力差即可。时间复杂度 nnn\sqrt n。

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
57
58
inline void clear(int x){
    cnt[x]=0;
    for(register int i=(x-1)*B+1,up=min(n,x*B);i<=up;++i){
        if(!i) continue;
        sm[x][g[i]]=0;
    }
}
inline void build(int x){
    for(register int i=(x-1)*B+1,up=min(n,x*B);i<=up;++i){
        g[i]+=tag[x];
        sm[x][g[i]]=(1LL*sm[x][g[i]]+f[i])%mod;
        if(g[i]<=K)
            cnt[x]=(1LL*cnt[x]+f[i])%mod;
    }
    tag[x]=0;
}
inline void pls(int x){
    if(tag[x]<=K) cnt[x]=(1LL*cnt[x]-sm[x][K-tag[x]]+mod)%mod;
    ++tag[x];
}
inline void dec(int x){
    --tag[x];
    if(tag[x]<=K) cnt[x]=(1LL*cnt[x]+sm[x][K-tag[x]])%mod;
}
inline void add(int l,int r,int val){
    if(l>r) return;
    clear(kid[l]);
    if(kid[l]==kid[r]){
        for(register int i=l;i<=r;++i)
            g[i]+=val;
        build(kid[l]);
        return;
    }
    for(register int i=l,up=kid[l]*B;i<=up;++i)
        g[i]+=val;
    build(kid[l]);
    clear(kid[r]);
    for(register int i=(kid[r]-1)*B+1;i<=r;++i)
        g[i]+=val;
    build(kid[r]);
    for(register int i=kid[l]+1;i<kid[r];++i){
        if(val>0) pls(i);
        else dec(i);
    }
}
// ...
for(register int i=1;i<=n;++i){
    int prp=lst[lst[i]];
    if(!prp) ++prp,g[0]-=(lst[i]>0?1:0);
    add(prp,lst[i]-1,-1);
    prp=lst[i];
    if(!prp) ++prp,++g[0];
    add(prp,i-1,1);
    f[i]=(g[0]<=K?1:0);
    for(register int j=1;j<=B;++j)
        f[i]=(1LL*f[i]+cnt[j])%mod;
    clear(kid[i]),build(kid[i]);
}

wqs 二分

如果直接设计状态发现复杂度爆炸，考虑一维是否有单调性，用 wqs 二分配合起来实现 DP 的优化。

具体而言，如果你要最优化的数和一些别的数存在凸函数关系，就可以考虑用 wqs 二分优化。这个思想可以运用在简单的二分一个维度，另一个维度用最优化类型的 DP 解决，还可以把题目转化为凸包问题求解一些奇怪的凸优化问题上。

【数据删除】

一个 nn 个点的图，每条边有两个权值 ai,bia_i,b_i。求一个生成树，最大化 (∑a)2+(∑b)2(\sum a)^2 + (\sum b)^2。

n,ai,bi≤103n,a_i,b_i\leq 10^3。

题解

貌似不好用朴素的 wqs + DP 的方法去解决它？

考虑第二个模型，如何把这个题变成一个凸包？

有凸包就要有二维平面，先整一个二维平面出来。将一棵树的 ∑a,∑b\sum a,\sum b 看作横纵坐标。用 wqs 二分求出这些点的凸包。显然答案一定在凸包上。

复杂度？凸包大小不超过最大权的 23\frac{2}{3} 次幂，因此复杂度为 (na)23log⁡(na)23(na)^{\frac{2}{3}}\log (na)^{\frac{2}{3}}。

矩阵、多项式

矩阵和经典多项式的优化都见怪不怪了，一般是用于递推式子的。

如果你看到这个题的模数非常 NTT，而且转移式子非常 NTT，或者转移式非常线性递推或非常卷积，数据范围非常奇怪，可以尝试往这个方面想一想，

当然也并不是所有的多项式优化 DP 的题都这么明显。还可能用生成函数、卷积过程中的性质辅助算法的瓶颈优化。

Luogu3746 组合数问题

有 nknk 个不同的物品，求选出的物品数模 kk 为 rr 的方案数。

n≤109,r<k≤50n\leq 10^9,r<k\leq 50。

题解

暴力转移设 fi,jf_{i,j} 表示选到第 ii 个物品，选了的物品数量模 kk 为 jj 的方案数：

fi,j=fi−1,j+fi−1,(j−1) mod kf_{i,j} = f_{i-1,j} + f_{i-1,(j-1)\bmod k}

显然可以用矩阵优化，观察转移方程不难得到：

[fnk,0fnk,1fnk,2fnk,3⋮fnk,k−1]=[1000⋯011100⋯000110⋯000011⋯00⋮⋱⋱⋱⋱⋱⋮0000⋯11]nk[1000⋮0]\begin{bmatrix}f_{nk,0} \\f_{nk,1} \\f_{nk,2} \\f_{nk,3} \\\vdots \\f_{nk,k-1}\end{bmatrix}=\begin{bmatrix}1 & 0 & 0 & 0 & \cdots & 0 & 1 \\1 & 1 & 0 & 0 & \cdots & 0 & 0 \\0 & 1 & 1 & 0 & \cdots & 0 & 0 \\0 & 0 & 1 & 1 & \cdots & 0 & 0 \\\vdots & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots \\0 & 0 & 0 & 0 & \cdots & 1 & 1\end{bmatrix}^{nk}\begin{bmatrix}1 \\0 \\0 \\0 \\\vdots \\0\end{bmatrix}

复杂度 k3log⁡(nk)k^3\log(nk)。

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
struct matrix{
    int a[max_n][max_n],n;
    inline void init(int x,string s){
        n=x;
        if(s=="zero"){
            memset(a,0,sizeof(a));
            return;
        }
        if(s=="epsilion"){
            memset(a,0,sizeof(a));
            for(register int i=1;i<=n;++i)
                a[i][i]=1;
            return;
        }
        if(s=="init"){
            memset(a,0,sizeof(a));
            for(register int i=1;i<=n;++i)
                ++a[i][i],++a[(i==1?n:(i-1))][i];
        }
    }

// ...

}f,g;

signed main(){
    // ...
    f.init(k,"zero"),f.a[1][1]=1;
    g.init(k,"init");
    f=f*Pow(g,n*k);
    write(f.a[1][r+1]);
}

【数据删除】

对于一个序列，令 li=max⁡{j∣aj>ai,j<i},ri=max⁡{j∣aj>ai,j>i}l_i = \max\{j|a_j>a_i,j<i\}, r_i = \max\{ j|a_j>a_i,j>i \}。若 lil_i 不存在，默认 00；若 rir_i 不存在，默认 n+1n+1。

多组询问，每次给定 KK，查询有多少大小为 nn 的排列满足：

∑i=1nmin⁡(i−li,ri−i)=K\sum_{i=1}^n \min(i-l_i, r_i-i) = K

n≤200,m≤20n\leq 200,m\leq 20。

题解

暴力设 fi,jf_{i,j} 表示长度为 ii 的排列，权值为 jj 的方案数。枚举排列最大数的位置，将其拆成两半：

fi,j=∑k=1i∑p=0j−l−min⁡(k,i−k+1)≥0(i−1k−1)fk−1,pfi−k,j−p−min⁡(k,i−k+1)f_{i,j} = \sum_{k=1}^i \sum_{p=0}^{j-l-\min(k,i-k+1)\geq 0} \binom{i-1}{k-1} f_{k-1,p} f_{i-k,j-p-\min(k,i-k+1)}

状态两维转移平方，复杂度不得爆炸。貌似没有其他方法做了，考虑生成函数优化。

设 Fi(x)F_i(x) 为 fif_i 的生成函数。有：

Fi=∑j=1i(i−1j−1)Fj−1Fi−jxmin⁡(j,i−j+1)F_i = \sum_{j=1}^i \binom{i-1}{j-1} F_{j-1} F_{i-j} x^{\min(j,i-j+1)}

考虑 FiF_i 次数的范围，显然当 K≤nlog⁡nK\leq n\log n 时答案才不是 00。因此 FF 次数不超过 nlog⁡nn\log n，就可以卷积了。

一开始就把 FiF_i 转成点值，每次查询时用拉插还原多项式。复杂度为 n3log⁡n+mn2log⁡2nn^3\log n+mn^2\log^2 n。

其他 Trick

随机化

对于数据规模小的时候，可以用一些诸如高幂级 DP、状压 DP 等做法解决的问题，数据规模较大时，可能可以通过随机化规约成小问题解决。

对于答案函数不具备单调性的时候，不能用朴素的二分/三分等做法，用 DP 来判定，其可能可以用模拟退火等做法模拟二分/wqs 二分，从而配合 DP 得到答案。

BZOJ5232 好题

给定一个节点带颜色的树，求最小的包含 kk 种颜色的连通块。

n≤104,k≤5n\leq 10^4,k\leq 5。

题解

如果颜色数很少怎么做？

对于颜色数很少的情况，fi,sf_{i,s} 表示考虑到 ii 号点，包含这个点且颜色状态为 ss 的最小连通块大小。转移显然。

考虑颜色很多的情况，把所有颜色随机 Hash 成 [1,k][1,k] 的颜色，跑上面的做法。重复若干次取最优答案。

正确性？

显然不会求出比正解更小的解出来。而对于正解连通块，其一定恰好包含 kk 种颜色。一次 Hash 跑一遍每个颜色都可以变成 [1,k][1,k] 中任意一个数，若这些数两两不同则可以找到正解。因此一次 Hash+DP 正确的概率为 k!kk\frac{k!}{k^k}。在 k=5k=5 的情况下，这个数很小。

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
inline void dfs(int u,int fa){
    f[u][1<<col[u]]=1;
    for(register int i=e.hd[u];i;i=e.nx[i]){
        int v=e.to[i];
        if(v==fa) continue;
        dfs(v,u);
        for(register int j=0;j<S;++j){
            if((j&(1<<col[u])) && f[u][j]!=inf)
                for(register int k=0;k<S;++k)
                    if(f[v][k]!=inf)
                        f[u][j|k]=min(f[u][j|k],f[u][j]+f[v][k]);
            if(__builtin_popcount(j)>=K)
                res=min(res,f[u][j]);
        }
    }
}

inline int sol(){
    for(register int i=1;i<=n;++i)
        for(register int j=0,up=vec[i].size(),c=rand()%K;j<up;++j)
            col[vec[i][j]]=c;
    res=n;
    memset(f,0x3f,sizeof(f));
    dfs(1,-1);
    return res;
}

复杂度平衡

这个词多用于 DS，但是 DP 也有这样的思想。具体和 DS 类似：考虑一种方法实现的转移在某方面很快，某方面很慢；另一种方式恰恰相反，则可以考虑如何将这两种方法进行结合，从而达到平衡复杂度的目的。

复杂度平衡的方式也因题而异。相对常见的比如直接将两个 DP 结合在一起。

Luogu3773 吉夫特

给定元素两两不同的序列 aa，求有多少长度不小于 22 的子序列满足：

∏i=2m(bi−1bi)≡1(mod2)\prod_{i=2}^m \binom{b_{i-1}}{b_i} \equiv1 \pmod 2

n≤2×105,ai<222n\leq 2\times 10^5,a_i<2^{22}。

题解

记 a=max⁡(ai)a=\max(a_i)。

考虑 Lucas 定理：

(bi−1bi)≡(bi−1 mod 2bi mod 2)(bi−12bi2)(mod2)\binom{b_{i-1}}{b_i} \equiv \binom{b_{i-1}\bmod 2}{b_i\bmod 2}\binom{\frac{b_{i-1}}{2}}{\frac{b_i}{2}} \pmod 2

不难发现这是二进制拆位的过程。这个条件可以转化为 bi−1b_{i-1} 的二进制是 bib_i 的子集。于是有暴力 DP：fif_i 表示考虑到第 ii 个数，找出的包含 aia_i 的合法子序列个数：

fi=∑j<i,aj⊂aifjf_i = \sum_{j<i,a_j\subset a_i} f_j

复杂度 n2log⁡an^2\log a。

考虑如下两种可行的优化方法：

  1. 记 gi=∑aj=ifjg_i = \sum_{a_j =i} f_j。每次增加一个数时 O(1)\mathcal O(1) 修改，转移 O(3log⁡a)\mathcal O(3^{\log a}) 枚举子集。
  2. 记 hi=∑aj⊂ifjh_i = \sum_{a_j\subset i} f_j。加数 O(3log⁡a)\mathcal O(3^{\log a}) 枚举超集修改，转移 O(1)\mathcal O(1) 查询。

这两种单独使用复杂度都是 3log⁡a3^{\log a}，考虑优化：

  • 转移时，固定 ii 二进制后一半，前一半枚举子集。
  • 查询时，固定 ii 二进制前一半，后一半枚举超集。

然后 g,hg,h 一起用。复杂度 6log⁡a26^{\log \frac{a}{2}}。

1
2
3
4
5
6
7
8
9
10
for(register int i=1;i<=n;++i){
    int l=a[i]&M,r=a[i]>>9;
    for(register int j=r;j<=M;j=(j+1)|r)
        g[i]=(g[i]+f[(j<<9)|l])%mod;
    for(register int j=l;;j=(j-1)&l){
        f[j|(r<<9)]=(f[j|(r<<9)]+g[i]+1)%mod;
        if(!j) break;
    }
    ans=(ans+g[i])%mod;
}

转移建图

AGC005D ～K perm counting

有多少大小为 nn 的排列满足 ∀i,∣pi−i∣≠K\forall i,\left|p_i-i\right|\neq K？

n≤2000n\leq 2000。

题解

考虑容斥，设 fif_i 为至少有 ii 个位置不符合条件的方案数。答案为：

∑i=0nfi(−1)i\sum_{i=0}^n f_i(-1)^i

考虑到对于一个数 xx，使其不满足条件的位置不超过 22 个。将 xx 向让 xx 不合法的位置连边，就可以得到 KK 条链：

pic-2

对每条链分别 DP：fi,j,0/1,0/1f_{i,j,0/1,0/1} 表示前 ii 个点有 jj 个不符合条件，xx 有没有选，x+Kx+K 有没有选的方案数。转移是分类讨论。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int tot=0;
for(register int i=1;i<=n;++i)
    if(!vis[i])
        for(register int j=i;j<=n;j+=K)
            vis[j]=1,a[++tot]=j;
a[0]=-(1<<30),f[0][0][0][0]=1;
for(register int i=1;i<=n;++i){
    f[i][0][0][0]=1;
    for(register int j=1;j<=i;++j){
        bool ok1=(a[i]-a[i-1]==K),ok2=(a[i+1]-a[i]==K);
        f[i][j][0][0]=(f[i-1][j][1][0]+f[i-1][j][0][0]+ok1*f[i-1][j-1][0][0])%P;
        f[i][j][0][1]=ok2*(f[i-1][j-1][1][0]+f[i-1][j-1][0][0])%P;
        f[i][j][1][0]=(f[i-1][j][0][1]+f[i-1][j][1][1]+ok1*f[i-1][j-1][0][1])%P;
        f[i][j][1][1]=ok2*(f[i-1][j-1][0][1]+f[i-1][j-1][1][1])%P;
    }
}

转化特殊情况

hiho1315 Reaching Permutations

给定一个大小为 nn 的排列。一次操作可以选出一个逆序对并交换。求经过若干次操作后可以得到多少不同的排列。

n≤20n\leq 20。

题解

不妨考虑一下 01 序列的情况吧。

正常情况是不好考虑的，考虑 01 序列。排列 AA 能经过若干次操作到达 BB 当且仅当 ∀i\forall i，BB 中第 ii 个 11 都不在 AA 中第 ii 个 11 的左边。

将 AA 转化成 nn 个 01 序列 aia_i。其中 ai,j=[Ai≥j]a_{i,j} = [A_i \geq j]。显然排列和 01 序列双射。而 AA 能到 BB 当且仅当 aia_i 能到 bib_i。必要性显然，充分性考虑：n→1n\to 1 枚举 ii，若要把 ii 从 ll 移到 rr，每次找到 (l,r](l,r] 中最大数所在的位置 xx，交换 l,xl,x。

于是做一个 01 串上的 DP：从全 00 串开始，每次转移将一个 00 改成 11，到达全 11 串。复杂度 n2nn2^n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for(register int s=0;s<S;++s) if(f[s]){
    int K=n-cal[s]+1,A=0;
    for(register int i=0;i<n;++i)
        if(a[i]>=K)
            A|=(1<<i);
    bool ok=1;
    for(register int i=1,p1=0,p2=0;i<=cal[s];++i,++p1,++p2){
        while(!(s&(1<<p1))) ++p1;
        while(!(A&(1<<p2))) ++p2;
        if(p1<p2){
            ok=0;
            break;
        }
    }
    if(!ok) continue;
    for(register int i=0;i<n;++i)
        if(!(s&(1<<i)))
            f[s|(1<<i)]=(f[s|(1<<i)]+f[s])%mod;
}
  • 标题: DP 入门
  • 作者: Arahc
  • 创建于 : 2022-06-21 08:00:00
  • 更新于 : 2023-03-16 13:55:34
  • 链接: https://arahc.github.io/2022/06/21/NOTE-DP/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
DP 入门
  1. 状态设计
    1. DP+DP
    2. 容斥原理
    3. DP of DP
    4. 状态数优化
  2. 转移优化
    1. 决策单调性
    2. 斜率优化
    3. DS 优化
    4. wqs 二分
    5. 矩阵、多项式
  3. 其他 Trick
    1. 随机化
    2. 复杂度平衡
    3. 转移建图
    4. 转化特殊情况