计数 DP 学习笔记

xuchuhan · 2024-09-26 17:11:49 · 算法·理论

前言

只是对遇到的计数类 dp 题目的记录，遇到了其他的难题也不一定会做。

题目实际上是蓝书的题目。文字也有不少是借鉴的蓝书题解。

简介

计数类 dp 强调不重不漏。因此，在求解计数类 dp 时，通常要找到一个“基准点”，围绕这个基准点构造一个不可划分的整体，避免子问题的重叠。

具体看几道题就知道这段话的意思了。

P10956 金字塔

一道区间 dp 和计数 dp 结合的题目。

不难想到状态：dp_{l,r} 表示 s_{[l,r]} 对应的合法金字塔方案数。

现在来探究序列的组成与划分。若 s_{[l,r]} 代表一棵树，那么 s_l,s_r 是进入和离开时根节点产生的。而 [l,r] 包含的每棵更深的子树也都代表了 s_{[l,r]} 的一段，相邻两段之间还包含了根节点的字符。

所以是否可以将 s_{[l,r]} 分成 2 部分，每部分包含若干棵子树呢？我们发现，这样并不是不重不漏的，显然，举个例子，AB|A 和 A|BA 都能划分出 A|B|A，而此时就出现了重复。

于是我们的计数方法：找基准点就出来了。我们只用考虑字串 s_{[l,r]} 的第一棵子树是由哪一段构成的，即枚举断点 k，使得第一棵子树代表的字符串是 f_{[l,k]}。这样转移必定是不重不漏的，因为当 k 不相同时，子树的大小必定不相同。

那么就有转移：若 s_l=s_r，则有 dp_{l,r}=dp_{l+1,r-1}+\sum_{l+2\leq k\leq r-2,s_l=s_k}dp_{l+1,k-1}\times dp_{k,r}；否则 dp_{l,r}=0。

初始有 dp_{i,i}=1，答案为 dp_{1,n}。

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=305,Mod=1e9;
int n;
string s;
int dp[N][N];
signed main(){
    cin>>s;
    n=s.size(),s=" "+s;
    for(int i=1;i<=n;i++)
        dp[i][i]=1;
    for(int l=3;l<=n;l+=2){
        for(int i=1;i+l-1<=n;i++){
            int j=i+l-1;
            if(s[i]!=s[j])
                continue;
            dp[i][j]=dp[i+1][j-1];
            for(int k=i+2;k<=j-2;k++)
                if(s[i]==s[k])
                    dp[i][j]+=dp[i+1][k-1]*dp[k][j],dp[i][j]%=Mod;
        }
    }
    cout<<dp[1][n];
    return 0;
}

P10982 连通图

同样考虑将问题划分成两个部分，其中一个为独立的不可划分的整体，作为我们的基准点。

因为连通图不好划分，考虑将问题转化为计算非连通图。那么就有 全集-非连通图个数=连通图个数。对于任何一个有 i 个节点的非连通图，它都由若干个连通块构成。我们不妨将基准点设在第一个连通块上，即枚举第一个连通块的节点个数 j，剩余部分的节点个数为 i-j。选出 j 个节点的方案数为 C_{i-1}^{j-1}，剩余 i-j 个节点任意排列，方案数为 2^{\frac{(i-j)\times(i-j-1)}{2}}。

所以，设 dp_i 表示 i 个节点的连通图数量，则有转移方程：dp_i=2^{\frac{i\times(i-1)}{2}}\sum_{j=1}^{i-1} dp_j\times C_{i-1}^{j-1}\times 2^{\frac{(i-j)\times(i-j-1)}{2}}，其中 2^{\frac{i\times(i-1)}{2}} 是全集的数量。

code:

#include<bits/stdc++.h>
#define int long long
#define Mod 1004535809
#define Inv(x,p) Fpow(x,p-2,p)
using namespace std;
const int N=1e3+5;
int n;
int fac[N]={1},dp[N];
int Fpow(int a,int b,int p){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%p;
        a=a*a%p,b>>=1;
    }
    return ans;
}
int C(int n,int m,int p){
    if(n<m)return 0;
    return ((fac[n]*Inv(fac[m],p))%p*Inv(fac[n-m],p))%p;
}
signed main(){
    cin>>n;
    for(int i=1;i<=1000;i++)
        fac[i]=fac[i-1]*i%Mod;
    dp[1]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++)
            dp[i]+=dp[j]*C(i-1,j-1,Mod)%Mod*Fpow(2,(i-j)*(i-j-1)/2,Mod)%Mod,dp[i]%=Mod;
        dp[i]=Fpow(2,i*(i-1)/2,Mod)-dp[i],dp[i]=((dp[i]%Mod)+Mod)%Mod;
    }
    cout<<dp[n];
    return 0;
}

P7690 [CEOI2002] A decorative fence

这里又要介绍计数 dp 的另一种 trick 了，它就是“试填法”。它主要是解决问排名为 x 的是哪一种数 or 方案。

拿这道题举例，我们从小到大枚举每一块木板的长度，当当前这一块木板的长度为 h 时，设后面的木板构成栅栏的方案数为 P，若 P\geq C，则说明当前这块木板的长度就为 h，退出尝试下一块木板的长度；否则模板应该更长，此时有 C\leftarrow C-P,h\leftarrow h+1。当然我们需要预处理 P。

设 dp_{i,j,1/0} 表示现在有 i 块木板可用，当前木板的长度排在 j 位，当前木板处于高/低位，那么易得转移：dp_{i,j,1}=\sum_{k=1}^{j}dp_{i-1,k,0},dp_{i,j,0}=\sum_{k=j}^{i-1}dp_{i-1,k,1}。初始时有：dp_{1,1,0}=dp_{1,1,1}=1。

试填的过程如上，但是需要注意，1 既可以处在高位，也可以处在低位，所以需要分类枚举。

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=25;
int T,n,m;
bool vis[N];
int dp[N][N][2];
void init(){
    dp[1][1][1]=dp[1][1][0]=1;
    for(int i=2;i<=20;i++){
        for(int j=1;j<=i;j++){
            for(int k=1;k<j;k++)
                dp[i][j][1]+=dp[i-1][k][0];
            for(int k=j;k<i;k++)
                dp[i][j][0]+=dp[i-1][k][1];
        }
    }
    return;
}
signed main(){
    init();cin>>T;
    while(T--){
        cin>>n>>m;
        int k,pre;
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++){//分类枚举1的状态 
            if(m>dp[n][i][1])m-=dp[n][i][1];
            else{k=0,pre=i;break;}
            if(m>dp[n][i][0])m-=dp[n][i][0];
            else{k=1,pre=i;break;}
        }
        vis[pre]=1;cout<<pre<<" ";
        for(int i=2;i<=n;i++){//一位一位确定状态 
            int rk=0;
            for(int j=1;j<=n;j++){//rk是长度j的排名 
                if(vis[j])continue;
                rk++;
                if((k&&j>pre)||(!k&&j<pre)){//符合要求 
                    if(m>dp[n-i+1][rk][k])m-=dp[n-i+1][rk][k];
                    else{k^=1,pre=j;break;}
                }
            }
            vis[pre]=1;cout<<pre<<" ";
        }
        cout<<"\n";
    }
    return 0;
}