DP

Fluorine Wang

2024-05-19

ACM

Algorithm

背包九讲

01背包无限背包多重背包组合背包

01背包是指物品只能选1次的背包问题.无限背包是每个物品能选无限个的问题,这俩的区别就是一个正着枚举一个倒着枚举.

多重背包 :你有n种物品,每样物品各自能买a个,每个b元有c的价值,求最大:想办法转化成01背包:使用二进制拆分,如(6=1+2+3,8=1+2+4+1),可以把原来的每种m个化成logm个加快效率.

组合背包 :这种背包就是前面背包的组合.直接分情况讨论即可.

普通DP

你每个月可以花bi元买hi的幸福值,你每个月末都会收到x元固定工资,求这么多月下来你的最大幸福值是多少.($m\le50,b_i\le1e9,x\le1e9,h_i\le1e3$)

首先发现这是一个dp,设dp[i][j]表示第i月剩下钱数为j的时候能有的最大幸福值(传统背包),发现会被卡,于是考虑枚举别的维度,发现幸福值非常小,于是枚举幸福值,设dp[i][j]表示第i月幸福值为j的时候的最大剩余钱数,同时省略月数维度,考虑转移:(正数转移)
$dp[j]=\max(dp[j],dp[j-h_i]-b_i)$
然后发工资就是全部都加上x.
CF2028D 有三个人,每个人有一个n的排列表示对于牌的珍惜程度,数字越大越珍惜,就越想得到.你希望从1换到n,中间换到的牌单调递增,问有没有可能的路径?如果有输出一种.举例: 3 4 1 2 说明一个人能用1去换3和4,用2去换3和4.

考虑dp,mins[3]表示三个人的从x能换到n的最小下标 ,chan[200010]表示能从这个点换到什么,倒着转移,如果一个人比mins[]要大,证明能换,此时考虑缩小另外两个(让他们尽可能小去换到更多的牌),chan在这里标记上,同时另外两个取最小值.

期望DP

期望dp的状态一般设定为 dp[i]:已经取到i个,取完剩下的期望xx ,转移方程一般写作 “概率转移+代价” 的形式.然后列转移方程.

有n种邮票,第k次买邮票的价格是k元,每次买邮票等概率随机一种,问一个人想买到这总共n种邮票期望花多少钱.

我们发现第k次取和价钱挂钩,于是要设两个式子: $f(x)$ 表示已经取到了x,取完总共n种的期望次数, $g(x)$ 表示已经取到了x,期望取完的价钱 .于是有
$f(x)=\frac xnf(x)+\frac{n-x}nf(x+1)+1$ $g(x)=\frac xn(g(x)+f(x)+1)+\frac{n-x}n(g(x+1)+f(x+1)+1)$
关于g的表达式:有x/n的概率不动,也就是期望不变,后面的f(x)是期望的代价是次数,+1表示每次都要比之前贵一块,体现在这里.
一个怪有n滴血,一次攻击有 $p$ 的概率掉两滴血, $1-p$ 的概率掉一滴血,求怪物死亡(血量小于等于0)的期望攻击次数.这个的dp是 怪物剩x滴血时的期望攻击次数 ,方程为
$dp_i=\begin{cases}0&i\ge n\\dp_{i+1}p+dp_{i+2}(1-p)+1&i<n\end{cases}$
这个1就是攻击代价.

压缩大小(不是滚动数组)

青蛙过河p1052,青蛙一次能跳[s,t]的距离,距离上有一些石块(小于100个),青蛙想知道跳过桥的长度l需要最少踩多少个石块,桥长1e9,一步最长10,起点在0.

显然的dp,但是桥的长度有点太长了,考虑优化.

首先特判一下s==t的情况.
72缩: 根据相邻两个数必互质的原则,后面的每一个点都是可以从一个点出发到达的,最大不可达点是能算出来的,于是根据这个进行缩点,1-10的最大不可表示点是71(10*9-9-10),所以如果有点之间的距离大于这个数就缩成这个数.

2520缩 : $\mathrm{lcm}(1,2,…,10)=2520$ ,意味着无论步长多少,一定可以到达2520这个点,所以按照2520分块,如果前方2520个点没有石头就直接忽略,有再dp.

整数划分

常见以下几种题型:

给一个数,划分成一些数(给n个硬币分成若干堆)问有多少种情况.(以及略微加强版,划分的最大数不超过m)

设 $p(n,m)$ 表示能划分的种类数,先考虑nm的关系:假如 $m\ge n$ ,那么就是p(n,n),由于包含最大划分数的只有一种,剩下的都不包含n.

然后是小于n的情况.存在最大划分数的时候有p(n-m,m)的情况,如果不存在,那么m就没有意义了,可以把范围放小,所以这个时候的情况就是p(n,m-1),总的式子就是下面的:
$p(n,m)=\begin{cases}1+p(n,n-1)&n\le m\\p(n-m,m)+p(n,m-1)&n>m\end{cases}$
由于分堆不限最大数,直接带入n即可.
将n划分成k个数的划分法

有两类:第一类是均分,所有都得到1,就是前面的式子.
第二类是拆一个1出去,得到后半部分.于是所有情况在dp之中被算出来了.
$dp[n][k]=dp[n-k][k]+dp[n-1][k-1]$
将n划分成多个不同的整数(m表示最大数)

分为两种情况:划分的每个数都小于m,就是前半部分,直接缩范围即可.
第二种情况是有一个数是m,则提出来,同时剩下的数都不能大于m,就是后半部分(发现和初始的情况很像,只是限制了以下最大值)
$dp[n][m]=dp[n][m-1]+dp[n-m][m]$
将n划分成若干奇数的划分法

设f(i,j)表示把数i分成j个偶数的情况,g(i,j)表示把数i分成j个奇数的情况.
$f[i][j]=g[i-j][j]\\g[i][j]=f[i-j][j]+g[i-1][j-1]$
理解起来也简单,偶数就等于所有划分成奇数的都添一个1变成偶数,奇数有从偶数变成奇数和在数列末尾加一个1两种情况.

拓展思考:为什么dp的时候都是只在末尾加上一个1,不是别的数?
因为整体垫高的缘故,往末尾加一个1可以保证不会大于之前的分拆,也就是说维护了数列单调性,进而保证情况不会重合.
问一个数字分成几个数字相乘有几种形式:

设dp ij表示前i位,总积为j的状况,可以nlog递推.
如果给一个很大的全是1的序列去排列这些数字,可以用dpij表示前i位总积位j且所有数均不为1的情况数,然后套组合数公式.

树形DP

p3574 设 $f[x]$ 表示 $x$ 子树内的最大值, $sz[x]$ 表示走完x的子树后回到x花的时间.考虑一个点的分叉y和z:不交换,遍历顺序是
$f[x]=max(f[x],size[x]+max(f[y],f[z]+size[y]+2)+1)$
交换之后遍历先z后y,答案是
$f[x]=max(f[x],size[x]+max(f[z],f[y]+size[z]+2)+1)$
于是按照 $sz[x]-f[x]$ 排序,然后贪心即可.

插入式DP

通性是:直接维护不好维护,考虑维护一堆连通块,最后把他们整体合并成一个连通块算答案.

设 $dp_{ij}$ 表示前i个元素,形成了j个连通块的情况数,有下面几种情况:

某个块的元素个数+1
当前有j个块,随机选一个都可以.
$f_{i,j}=f_{i-1,j}\times j$
新增一个块
类似插空,因为原来有j-1个块,所以有j个空.
$f_{i,j}=f_{i-1,j-1}\times j$

合并两个块
这个时候不能在两端了,但是合并前应该有j+1个块,所以还是j个空.

$f_{i,j}=f_{i-1,j+1}\times j$

例1 p5999

有一个排列,起始是s,末尾是t,中间的所有元素满足这个元素两边相邻元素都大于或小于当前元素,问有多少种排列.

我们从小到大枚举元素,这样新插进来的元素两端一定小于该元素,一定合法.
假如元素比s和t都小,那么随便插,不然的话因为s或t的限制不能在一端/两端插入新块.
合并:可以.
当前块内元素+1:不合法.

例2 cf1515e

有一排灯,初始全部关闭,你想把他们全部打开.
你每次只能开一盏灯.假如一盏灯左侧和右侧的灯全部被点亮,这盏灯会自动亮起来.
现在你想知道有多少种方式能把灯全部打开.(不能打开已经打开的灯)

令 $f_{i,j}$ 表示已开机i台，构成了j个连续段，每段间距离是大于1的一个不确定值
转移有 新建段，段扩增，段合并 共五种情况

const int N=405;
int n,f[N][N],mod;

signed main(){
    read(n);read(mod);
    f[0][0]=1;
    for(int i=0;i<n;i++) for(int j=0;j<=i;j++){
        f[i+1][j+1]=(f[i+1][j+1]+f[i][j]*(j+1))%mod; //j+1个间隔选一个插
        f[i+1][j]=(f[i+1][j]+f[i][j]*j*2)%mod; //两端贴着开
        f[i+2][j]=(f[i+2][j]+f[i][j]*j*2)%mod; //两端隔一个开
        if(j>=2){
            f[i+2][j-1]=(f[i+2][j-1]+f[i][j]*(j-1)*2)%mod; //定两段间距离为2，有正反两种开法
            f[i+3][j-1]=(f[i+3][j-1]+f[i][j]*(j-1))%mod; //定两段间距离为3，开中间那个
        }
    }
    write(f[n][1]);
}

值域dp

比较典型的例子就是,你需要构造几个集合,满足他们相等.

task1 abc375e

你有三个组n个人,初始时每个人有一个分组a和战力b,一组的战力定义为所有组员战力总和,一个人必须在一个组里.问想让三个组战力相等需要至少调换多少人的初始组?
(n<=100,sum b<=1500)

dp,设 dp[num][i][j] 表示枚举了num个人,第一组战力为i,第二组战力为j,剩下的全部是第三个组的最小交换情况.
那么我们可以滚动转移,代码如下:

sum/=3;
int inf=114514;
for(int i=0;i<=sum;++i){
    for(int j=0;j<=sum;++j){
        dp[ff][i][j]=inf;
    }
}
ff=0;
dp[ff][0][0]=0;
for(int i=1;i<=n;++i){
    ff^=1;
    for(int j=0;j<=sum;++j){
        for(int k=0;k<=sum;++k){
            dp[ff][j][k]=inf;
        }
    }
    for(int j=0;j<=sum;++j){
        for(int k=0;k<=sum;++k){
            if(b[i]<=j){
                if(a[i]==1)    dp[ff][j][k]=min(dp[ff][j][k],dp[ff^1][j-b[i]][k]);
                else        dp[ff][j][k]=min(dp[ff][j][k],dp[ff^1][j-b[i]][k]+1);
            }
            if(b[i]<=k){
                if(a[i]==2)    dp[ff][j][k]=min(dp[ff][j][k],dp[ff^1][j][k-b[i]]);
                else        dp[ff][j][k]=min(dp[ff][j][k],dp[ff^1][j][k-b[i]]+1);
            }
            if(a[i]==3)        dp[ff][j][k]=min(dp[ff][j][k],dp[ff^1][j][k]);
            else            dp[ff][j][k]=min(dp[ff][j][k],dp[ff^1][j][k]+1);
        }
    }
}

task2 P1651

你有n个木头,高度为ai.你要用这里面的一些木头拼成两个塔,塔的高度分别是选择的木头的高度和,木头只能被选一次,可以不被选,塔的高度不能为0,你要输出最高塔的高度,没有就输出-1.
(对于 100% 的数据，N≤50 ,所有木块的高度总和 ≤500000。)

dp.因为这个题让我们输出最高高度,所以我们用dp[i]维护最高高度.
因为两个塔最终要相等,所以我们考虑维护dp[i]表示左塔-右塔=i时的左塔最高高度,加上一个偏移即可.

const int lim=1000100;
int eta=500000;
int inf=1e7;

int dat[100];
int dp[2][lim];

long long n,m,res;
int main(){
    fin>>n;
    for(int i=1;i<=n;++i){
        fin>>dat[i];
    }
    int ff=0;
    for(int j=0;j<lim;++j){
        dp[ff][j]=-inf;
    }
    dp[ff][eta]=0;
    for(int i=1;i<=n;++i){
        ff^=1;
        for(int j=0;j<lim;++j){
            dp[ff][j]=dp[ff^1][j];//如果强制每个木头都得选,那么这里改成-inf
        }//其实ff的转移完全是不必要的,这里有点多此一举了.
        for(int j=0;j<lim;++j){
            if(j+dat[i]<lim)    dp[ff][j]=max(dp[ff][j],dp[ff^1][j+dat[i]]+dat[i]);
            if(0<=j-dat[i])        dp[ff][j]=max(dp[ff][j],dp[ff^1][j-dat[i]]);
        }
    }
    if(dp[ff][eta]>0){
        fout<<dp[ff][eta];
    }else{
        fout<<-1;
    }
    return 0;
}

决策DP

这类题目的长相奇形怪状,反正最后就是DP.
大致流程为设状态模型->列出dp式子(发现有后效性)->消除后效性,开始计算.

矩阵优化

指通过广义矩阵乘法让dp的方式优化,支持数据结构维护的操作.

定义广义矩阵乘法的操作是:

$C_{i,j}=\bigoplus_{k=1}^m(A_{ik}\otimes B_{kj})$

(其实就是重载+和俩运算符)满足以下条件时乘法有 *结合律:

$\oplus$ 有交换律
$\otimes$ 有结合律和交换律
$\times$ 对 $\oplus$ 有分配律,也就是满足 $(a\oplus b)\otimes c=(a\otimes c)\oplus(b\otimes c)$ .

常见的广义矩阵重载是(原来是 $(\times,+)$ ) $(\pm,\min),(\pm,\max),(\land,\lor)$

如此,矩阵可以使用快速幂优化,同时可以使用数据结构提前维护区间矩阵乘积,便于快速计算.

杂题选做

GSS3单点修改,维护区间的最大子段和.
我们设 $f_i$ 表示以i结尾的最大子段和, $g_i$ 表示区间上的最大子段和.转移方程:
$f_i=\max(f_{i-1}+a_i,a_i),g_i=\max(g_{i-1},f_{i-1}+a_i,a_i)$
构造矩阵:
$\begin{bmatrix}f_{i-1}&g_{i-1}&0\end{bmatrix}\begin{bmatrix}a_i&a_i&-\infty\\-\infty&0&-\infty\\a_i&a_i&0\end{bmatrix}=\begin{bmatrix}f_i&g_i&0\end{bmatrix}$
然后使用线段树提前维护区间矩阵乘积即可.
设排列中一个完美三元组(i,j,k)满足 $p_i>p_j<p_k$ ,求长度为n的排列有多少种恰好有m个完美三元组.($i\le100,j\le10000$)特别奇怪的数据范围

因为排列里面插一个元素是不影响前面的,考虑DP.设dp[i][j]表示当前排列有i个元素时候有j个完美三元组的,发现,我们插一个1,由于1小于其他任何元素,新插1的贡献是能算出来的.于是直接背包,复杂度 $O(n^2m)$ .

一对集合(看不懂题解)
定义 $f(S)=(a_1,a_2,...,a_n)^{\gcd(a_i,a_2,...,a_n)}$ 完美集合对p,q是元素不重,而且p的所有元素比q的所有元素小,求给定数列a的 $\sum_{p\subset a}\sum_{q\subset a}f(p)\times f(q)\mod998244353$ ,其中qp是完美集合对. $n\le100,0\le a_i\le100$

这个题数据范围和元素范围都小的离谱,而且暴搜是过不去的,所以考虑dp(好像所有数据范围非常奇怪的都是dp,或者网络流).
首先对a进行排序.
设 $f_{i,d,j}$ 表示前i个元素,最大公约数是d的所有集合的和的j次方之和.有

$f_{i,d,j}=\sum_{p=0}^{j}\binom{j}{p}f_{i-1,x,p}a_{i}^{j-p}$

其中x满足 $\gcd(x,ai)=d$ .
设 $$g{i,d,j}$$ 表示后i个元素,gcd是d的所有集合的j次方之和,一样的转移方程.

最后统计答案只需要枚举每一个必须选的元素,然后使用fg计算答案.
没准之后学组合数学了就能看懂了.

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
const int mod=998244353;
int datas[maxn];
int a[maxn][101],n;
int f[maxn][101][101],C[101][101];
int g[maxn][101][101];
int gcd(int a,int b){ if(b==0)return a; return gcd(b,a%b);}
int ksm(int a,int b){ int res=1; while(b){ if(b&1){ res=1ll*res*a%mod; } a=1ll*a*a%mod; b>>=1; } return res;}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>datas[i];
    }
    sort(datas+1,datas+1+n);
    for(int i=1;i<=n;i++){
        a[i][0]=1;
        for(int j=1;j<=100;j++){
            a[i][j]=1ll*a[i][j-1]*datas[i]%mod;
        }
    }//a[i][j]表示元素a[i]的j次方

    C[0][0]=1;
    for(int i=1;i<=100;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++){
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
        }
    }//处理组合数
    f[0][0][0]=1;
    for(int i=1;i<=n;i++){
        for(int x=0;x<=100;x++){
            for(int y=0;y<=100;y++){
                f[i][x][y]=f[i-1][x][y];
            }
        }
        for(int x=0;x<=100;x++){
            int d=gcd(x,a[i][1]);
            for(int j=0;j<=100;j++){
                for(int p=0;p<=j;p++){
                    f[i][d][j]+=1ll*C[j][p]*f[i-1][x][p]%mod*a[i][j-p]%mod;
                    f[i][d][j]%=mod;
                }
            }
        } 
    }
    g[n+1][0][0]=1;
    for(int i=n;i>=1;i--){
        for(int x=0;x<=100;x++){
            for(int y=0;y<=100;y++){
                g[i][x][y]=g[i+1][x][y];
            }
        }
        for(int x=0;x<=100;x++){
            int d=gcd(x,a[i][1]);
            for(int j=0;j<=100;j++){
                for(int p=0;p<=j;p++){
                    g[i][d][j]+=1ll*C[j][p]*g[i+1][x][p]%mod*a[i][j-p]%mod;
                    g[i][d][j]%=mod;
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<n;i++){//必须选的那个数
        int res1=0;
        for(int x=0;x<=100;x++){//除掉这个元素之外元素的最大公约数
            int d=gcd(x,a[i][1]);//整个集合的最大公约数
            for(int p=0;p<=d;p++){//次方
                res1+=1ll*C[d][p]*f[i-1][x][p]%mod*a[i][d-p]%mod;
                res1%=mod;
            }
        }
        int res2=0;
        for(int j=1;j<=100;j++){
            res2=(res2+g[i+1][j][j])%mod;
        }
        ans=(ans+1ll*res1*res2%mod)%mod;
    }
    cout<<ans<<endl;
    return 0;
}

有n个数,两个人每次随机从n个选一个,如果选过就要掏1块钱,n个都选过之后游戏结束,求两个人各自掏钱期望.

用 $f1_i$ 表示抽到过的卡牌数变成 $i$ 的那刻,先手的罚款期望值.用 $f2_i$ 表示抽到过的卡牌数量变成 $i$ 的那刻,后手的罚款期望值.
转移方程:$f1_{i+1}=f1_i+A.$
$A$表示数量变成i的那刻到数量变成i+1的那刻这段时间里，先手的
罚款期望值。
那怎么求 $A$ 呢？
显然，$A$是一条级数式，而常数项相同的级数式较易求和。设$h1=$抽到过的卡牌数量变成$i$后轮到
先手的概率，$h2=$抽到过的卡牌数量变成$i$ 后轮到后手的概率，则有：
$A=(h1\times\frac{i}{n}+h1\times\frac{i}{n}\times\frac{i}{n}\times\frac{i}{n}+...)+(h2\times\frac{i}{n}\times\frac{i}{n}+h2\times\frac{i}{n}\times\frac{i}{n}\times\frac{i}{n}\times\frac{i}{n})$ $=h1\times\frac{i}{n}\times(1+(\frac{i}{n})^{2}+(\frac{i}{n})^{4}+...)+h2\times(\frac{i}{n})^{2}\times(1+(\frac{i}{n})^{2}+(\frac{i}{n})^{4}+...)$
设 $p=\frac in$,则$1+(\frac in)^2+(\frac in)^4+...=\frac1{1-p^2}.$
$A= h1\times \frac p{1- p^2}+ h2\times \frac {p^2}{1- p^2}$$ . 代入原式，$$f1_i+1=f1_i+h1\times\frac p{1-p^2}+h2\times\frac{p^2}{1-p^2}.$
同理，$f2_{i+1}=f2_i+h2\times\frac p{1-p^2}+h1\times\frac{p^2}{1-p^2}.$

问题：怎么求 $h1,h2$ 呢？
用$h1_i$表示“抽到过的卡牌数虽变成$i$后轮到先手的概率”。用$h2_i$表示“抽到过的卡牌数量变成$i$后轮到后手的概率”。边界：$h1_1=0,h2_1=1$。
$\begin{aligned}h1_{i+1}&=(h1_{i}\times p\times(1-p)+h1_{i}\times p\times p\times p\times(1-p)+...)+(h2_{i}\times(1-p)+h2_{i}\times p\times p\times(1-p)+...)\\&=h1\times p\times(1-p)\times\frac{1}{1\:p^{2}}+h2\times(1-p)\times\frac{1}{1\:p^{2}}\\&=\frac{1}{1+p}\times(h1\times p+h2),\\&\text{同理,}h2_{i+1}=\frac{1}{1+p}\times(h2\times p+h1),\end{aligned}$
最终答案为$(f1_n,f2_n)$。

另解
我们设f(x)表示作为先手，当前有x个物品已经被摸到的期望代价，同理设g(x)代表后手的相应情况.

对于每一次摸球，我们只有摸到新的和摸到旧的两种可能。
摸到新的，概率是 $\frac{n-x}n$ ,此时有
$\begin{cases}f(x)=g(x+1),\\g(x)=f(x+1)\end{cases}$
摸到旧的，概率是 $\frac{x}{n}$ 此时
$\begin{cases}f(x)=g(x)+1,\\g(x)=f(x)\end{cases}$
交换先后手操作为什么后手没有+1,是因为先手已经加过了,而后手是转移到先手上的.于是导一下式子即可.
给一个数n,输出有n个因数的数字(比如给定4输出6,因为6有1 2 3 6四个因子), $1\le n\le5e4$ .

这个题要用dp.首先根据因数分解定理,设一种分解 $n=p_1p_2…p_n$ ,有最小结果 $res=2^{p_1-1}3^{p_2-1}…$ 于是因为log2(50000)=16,最多用到16个质数.

设dp[i][j]表示有i个因数,只使用前j个质数时的结果,显然有转移方程
$dp_{i,j}=\min\left(dp_{\frac{i}{k},j-1}p_{j}^{k-1}\right)$
如果是质数的时候是2的好几万次方,显然要用高精.但是高精dp不好搞,于是对上式取ln,得到
$dp_{i,j}=\min\left(dp_{\frac{i}{k},j-1}+(k-1)p_{j}\right)$
然后记录dp的过程(说的简单)倒推就行了.具体实现是记录转移的过程,然后使用dp相减之后取exp得到原先乘的数字加到高精里面去,经测验不会掉精度.
多重背包,每次有一种不能选,每次询问有新的金币数,求最大价值和.
两遍多重背包,最后拼一起就行了.
标答是cdq分治或者线段树分治,不会…
CF2073A 容斥DP,非常的仙.要求四个塔每两个塔在一行或一列,可以用dp[num][i][j]表示第num个塔坐标ij的情况数,我们可以强制两个相邻的塔不在一起,现在要考虑A=C或B=D或A=D的情况:A=C时就是sum(dp[3]xx),B=D也一样,当这两个重合时就是sum(dp[2]xx),容斥即可.最后是A=D,发现此时四个塔都在一行或一列,直接统计减掉即可.
CCPC网络赛一个题,求解字符串S’中以子序列形式出现了多少T.
先考虑S中出现多少个T:设dp[l][r]表示有一个子串匹配上了T[l,r],然后以长度进行转移.

然后考虑S’对T的影响:原先每个字符匹配上的[l,r]不变,然后原先不成对的区间可能合并,使用lr转移,然后再考虑中间新加的字符有什么影响.
abc225_f
为了消除字符串长度不一造成的影响,我们应当倒着dp.