一些 DP 手法

xujindong_ · 2025-11-05 17:35:04 · 个人记录

笛卡尔树上 DP

通常用于处理排列/序列最值相关的限制，一般形如区间 DP f_{l,r}。

这类题能用区间 DP 处理的原因是这个区间确定最值的位置后，跨越这个点的 \min 或 \max 都确定，劈成的两个区间是相对独立的。这个结构是最大值/最小值的分治树，也就是笛卡尔树。

另一种情况是这个序列上的元素按时间依次出现/消失。如果满足一个位置出现/消失后分开的两段独立，也可以区间 DP，相当于时间的笛卡尔树。

有些时候 DP 值和具体区间无关，就可以优化到只有一维长度。

P6453

笛卡尔树+树形dp。

如图，对图形自底向上划分成若干个矩形，发现这些矩形形成一个树形的结构，而且满足祖先的 h 更小。那么可以以 x 为编号，y 为 h 建立小根笛卡尔树，其中节点 u 的长为 size_u，宽为 h_u-h_{fa_u}。这样划分后兄弟节点是独立的，可以树形 DP。

设 f_{i,j} 表示节点 i 的子树中选 j 个的方案数，类似树上背包用乘法原理合并即可。

这一题中没有依赖关系，因此对节点本身需要单独合并。若当前矩形选了 k 个，则当前矩形的方案为 C_{size_i-(j-k)}^kC_{h_u-h_{fa_u}}^kk!。

#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
int n,m,st[505],h[505],rt,s[505];
long long f[505][505],fac[1000005],vac[1000005];
struct node{
  int ls,rs;
}tr[505];
template<typename T>T qpow(T a,T b,T n,T ans=1){
  for(a%=n;b;b>>=1)b&1&&(ans=1ll*ans*a%n),a=1ll*a*a%n;
  return ans;
}
template<typename T>T inv(T a,T b){
  return qpow(a,b-2,b);
}
template<typename T>void inv_fac(int n,T p,T fac[],T vac[]){
  fac[0]=1;
  for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%p;
  vac[0]=1,vac[n]=inv(fac[n],p);
  for(int i=n-1;i>=1;i--)vac[i]=vac[i+1]*(i+1)%p;
}
int build(int n,int a[]){
  for(int i=1,top=0;i<=n;i++){
    while(top&&a[st[top]]>a[i])tr[i].ls=st[top--];
    if(top)tr[st[top]].rs=i;
    st[++top]=i;
  }
  return st[1];
}
long long C(int n,int m){
  return fac[n]*vac[m]%mod*vac[n-m]%mod;
}
void dfs(int pos,int fa){
  f[pos][0]=s[pos]=1;
  if(tr[pos].ls){
    dfs(tr[pos].ls,pos),s[pos]+=s[tr[pos].ls];
    for(int i=min(s[pos],m);i>=1;i--)for(int j=1;j<=min(s[tr[pos].ls],i);j++)f[pos][i]=(f[pos][i]+f[tr[pos].ls][j]*f[pos][i-j]%mod)%mod;
  }
  if(tr[pos].rs){
    dfs(tr[pos].rs,pos),s[pos]+=s[tr[pos].rs];
    for(int i=min(s[pos],m);i>=1;i--)for(int j=1;j<=min(s[tr[pos].rs],i);j++)f[pos][i]=(f[pos][i]+f[tr[pos].rs][j]*f[pos][i-j]%mod)%mod;
  }
  for(int i=min(s[pos],m);i>=1;i--)for(int j=1;j<=min(h[pos]-h[fa],i);j++)f[pos][i]=(f[pos][i]+fac[j]*f[pos][i-j]%mod*C(h[pos]-h[fa],j)%mod*C(s[pos]-i+j,j)%mod)%mod;
}
int main(){
  cin>>n>>m,inv_fac(1000000,mod,fac,vac);
  for(int i=1;i<=n;i++)cin>>h[i];
  return rt=build(n,h),dfs(rt,0),cout<<f[rt][m]<<'\n',0;
}

CF1580D

建出笛卡尔树，在笛卡尔树上 DP。

设 f_{pos,k} 为在节点 pos 的子树里选 k 个的最大值，枚举左右子树分别选了 i,j 个。由于 pos 是子树所代表的区间中最小的，因此每个跨越 pos 的区间的 f 都为 a_{pos}。则有 f_{pos,i+j}\gets\max(f_{pos,i+j},f_{ls,i}+f_{rs,j}-2ija_{pos}),f_{pos,i+j+1}\gets\max(f_{pos,i+j+1},f_{ls,i}+f_{rs,j}-(2ij+2i+2j)a_{pos})。

#include<bits/stdc++.h>
using namespace std;
int n,m,rt,st[4005],s[4005],top;
long long a[4005],f[4005][4005];
struct node{
  int ls,rs;
}tr[4005];
int build(int n,int a[]){
  for(int i=1;i<=n;i++){
    while(top&&a[st[top]]>a[i])tr[i].ls=st[top--];
    if(top)tr[st[top]].rs=i;
    st[++top]=i;
  }
  return st[1];
}
void dfs(int pos){
  s[pos]=1;
  if(tr[pos].ls)dfs(tr[pos].ls),s[pos]+=s[tr[pos].ls];
  if(tr[pos].rs)dfs(tr[pos].rs),s[pos]+=s[tr[pos].rs];
  for(int i=0;i<=s[tr[pos].ls];i++){
    for(int j=0;j<=s[tr[pos].rs];j++){
      f[pos][i+j]=max(f[pos][i+j],f[tr[pos].ls][i]+f[tr[pos].rs][j]-2ll*i*j*a[pos]);
      f[pos][i+j+1]=max(f[pos][i+j+1],f[tr[pos].ls][i]+f[tr[pos].rs][j]+m*a[pos]-(2ll*(i+1)*(j+1)-1)*a[pos]);
    }
  }
}
int main(){
  memset(f,-0x3f,sizeof(f)),f[0][0]=0,cin>>n>>m;
  for(int i=1;i<=n;i++)cin>>a[i];
  return rt=build(n,a),dfs(rt),cout<<f[rt][m]<<'\n',0;
}

进一步地，可以不建出树，而是按最小值分治。

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long a[4005];
vector<long long>solve(int l,int r){
  vector<long long>f(r-l+2,-0x3f3f3f3f3f3f3f3f);
  f[0]=0;
  if(l>r)return f;
  int pos=l;
  for(int i=l;i<=r;i++)if(a[i]<a[pos])pos=i;
  vector<long long>fl=solve(l,pos-1),fr=solve(pos+1,r);
  for(int i=0;i<fl.size();i++){
    for(int j=0;j<fr.size();j++){
      f[i+j]=max(f[i+j],fl[i]+fr[j]-2ll*i*j*a[pos]);
      f[i+j+1]=max(f[i+j+1],fl[i]+fr[j]+m*a[pos]-(2ll*(i+1)*(j+1)-1)*a[pos]);
    }
  }
  return f;
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++)cin>>a[i];
  return cout<<solve(1,n)[m]<<'\n',0;
}

AT_agc028_b

移除的过程可以看成按删除时间分治。建出关于删除时间的小根笛卡尔树，则每个节点的代价是其子树。

算贡献，每个节点的贡献为其深度。考虑求每个节点深度的期望，对于节点 u<v，u 是 v 的祖先的条件是 u 是 [u,v] 中删除最晚的节点，因为排列均匀，所以概率是 \frac 1{v-u+1}。u>v 同理。则每个节点的期望深度可以表示为 \sum_{i=1}^{u}\frac 1i+\sum_{i=1}^{n-u+1}\frac 1i-1。预处理 sum_i 表示倒数前缀和，答案为 n!\prod_{i=1}^n a_i(sum_i+sum_{n-i+1}-1)。

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int n,sum[100005],ans;
int main(){
  sum[0]=sum[1]=1,cin>>n;
  for(int i=2;i<=n;i++)sum[i]=1ll*sum[mod%i]*(mod-mod/i)%mod;
  for(int i=2;i<=n;i++)sum[i]=(sum[i]+sum[i-1])%mod;
  for(int i=1,a;i<=n;i++)cin>>a,ans=(ans+1ll*(1ll*sum[i]+sum[n-i+1]-1)*a%mod)%mod;
  for(int i=1;i<=n;i++)ans=1ll*ans*i%mod;
  return cout<<ans<<'\n',0;
}

CF2129D

考虑用笛卡尔树式的区间 DP 刻画这个加分，好处是这样刻画了变成黑格的先后顺序。且一个区间左右两端变成了黑色，里面的就只能加到内部。设 f_{l,r,x,y} 为区间 [l,r]，让 l-1 加了 x 分，r+1 加了 y 分的方案数。转移枚举这个区间内首个染色的，以及左右两个区间给分段点加了多少。

可以观察到，分数不超过 O(\log n)。这是因为对于黑格 i，右边 j 给 i 加了一分，接下来 k 给 i 加分距离会减半，左边也一样。复杂度 O(n^3\log^3n)。更好的做法是若 s_{l-1}=-1，我们就不再关心 x 了，对 r+1 同理，因此可以把状态合并。此时 l,r,i 的枚举量是 \sum s_i[s_i\ne-1]+[s_i=-1]。而一组合法的 s 的和是不会超过 n-1 的，因此复杂度 O(n^3)。

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int t,n,s[105],fac[105],vac[105],f[105][105][15][15];
int C(int n,int m){
  return n<0||m<0||n<m?0:1ll*fac[n]*vac[m]%mod*vac[n-m]%mod;
}
int main(){
  fac[0]=vac[0]=vac[1]=1;
  for(int i=2;i<=100;i++)vac[i]=1ll*vac[mod%i]*(mod-mod/i)%mod;
  for(int i=1;i<=100;i++)fac[i]=1ll*fac[i-1]*i%mod,vac[i]=1ll*vac[i]*vac[i-1]%mod;
  cin>>t;
  while(t--){
    cin>>n;
    int sum=0,lim=2*__lg(n);
    bool flag=0;
    for(int i=1;i<=n;i++)cin>>s[i],flag|=s[i]>lim,sum+=s[i]==-1?0:s[i];
    if(flag||sum>n){
      puts("0");
      continue;
    }
    s[0]=s[n+1]=-1;
    for(int i=1;i<=n+1;i++)f[i][i-1][0][0]=1;
    for(int len=1;len<=n;len++){
      for(int l=1,r=len;r<=n;l++,r++){
        for(int a=0;a<=(s[l-1]==-1?0:s[l-1]);a++){
          for(int b=0;b<=(s[r+1]==-1?0:s[r+1]);b++){
            for(int i=l;i<=r;i++){
              bool fl,fr;
              if(l!=1&&r!=n){
                if(i-l<=r-i)fl=1,fr=0;
                else fl=0,fr=1;
              }
              else fl=l!=1,fr=r!=n;
              int na=s[l-1]==-1?a:a-fl,nb=s[r+1]==-1?b:b-fr;
              if(na<0||nb<0)continue;
              if(s[i]==-1)f[l][r][a][b]=(f[l][r][a][b]+1ll*f[l][i-1][na][0]*f[i+1][r][0][nb]%mod*C(r-l,i-l))%mod;
              else for(int x=0;x<=s[i];x++)f[l][r][a][b]=(f[l][r][a][b]+1ll*f[l][i-1][na][x]*f[i+1][r][s[i]-x][nb]%mod*C(r-l,i-l))%mod;
            }
          }
        }
      }
    }
    cout<<f[1][n][0][0]<<'\n';
    for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)for(int a=0;a<=lim;a++)for(int b=0;b<=lim;b++)f[i][j][a][b]=0;
  }
  return 0;
}

连续段 DP

常用于刻画排列/按顺序出现中相邻位置的大小关系限制。

假如要刻画排列中相邻元素的限制，假设就从前往后插入，就只能相对插入，无法得知具体值。按值域插入相对位置又无法得知当前每个空隙之后会不会来数。

考虑钦定每个空隙以后还会不会来数，这会使已有的元素被确定为若干连续段。我们要求最后的连续段数是 1，因此这些空隙之后一定有数。这些段是浮动的，我们不确定段间的距离。这样我们就知道了每个数插入时两边有没有数，也能维护相邻位置的大小关系。

具体来说，记一下连续段数，转移可能有合并两段、插在一段左或右、单独成段。有些情况要特殊处理最左和最右，记一下左右是否还能插入的 0/1/2，多两种转移，插在最左最右并决定是否封口。

P5999

设 p_i 为第 i 步所在的位置。假如按位置插入，无法保证 p_1=s。考虑按走到的时间插入并维护连续段。此时大小关系的限制相当于插入只能合并两个块或新开一个块。强制 s,t 必须插在两端即可。

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int n,s,t,f[2005][2005];
int main(){
  f[1][1]=1,cin>>n>>s>>t;
  for(int i=2;i<=n;i++){
    for(int j=1;j<=i;j++){
      if(i!=s&&i!=t)f[i][j]=(1ll*(j-(i>s)-(i>t))*f[i-1][j-1]+1ll*j*f[i-1][j+1])%mod;
      else f[i][j]=(f[i-1][j]+f[i-1][j-1])%mod;
    }
  }
  return cout<<f[n][1]<<'\n',0;
}

P9197

考虑按值域从小往大插入，此时可以将绝对值拆开，先插入的减，后插入的加。插入时看左右两边有没有数，产生 -2\sim2 次的贡献。

插入时，我们需要钦定左右两边必须有/没有更大的数会插入。这样钦定后，会形成若干的连续段，最后要求全部并成一段，所以不会出现钦定有数插入，但实际上没有的情况。边界处的贡献不同，同理可以钦定为边界，最后要求两个边界都被使用。设 f_{i,j,k,0/1/2} 为插入的数、连续段数、当前和、剩余边界数，转移有 5 种：单独成段不在边界、单独成段在边界、并到某段左右不在边界、并到某段左右在边界、合并两段。

这样有个问题，权值的和有加有减，因此第二维必须开到 O(n^2)。考虑将 a_i-a_j 拆成 \sum_{k=j}^{i-1}a_k-a_{k-1}。这就是说，当前有 2j-l 个还没封口的连续段端点，产生 (2j-l)(a_i-a_{i-1}) 的和。这也可以视为计算折线图上 a_i 以下部分的线段长度和。因为和只增加，第二维只用开到 L。

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int n,m,a[105],f[2][105][1005][3],ans;
int main(){
  f[0][0][0][0]=1,cin>>n>>m;
  for(int i=1;i<=n;i++)cin>>a[i];
  if(n==1)return puts("1"),0;
  sort(a+1,a+n+1);
  for(int i=1;i<=n;i++){
    memset(f[i&1],0,sizeof(f[i&1]));
    for(int j=0;j<i;j++){
      for(int l=0;l<=2;l++){
        for(int k=0;k<=m-(a[i]-a[i-1])*(2*j-l);k++){
          if(!f[~i&1][j][k][l])continue;
          int sum=k+(a[i]-a[i-1])*(2*j-l);
          f[i&1][j+1][sum][l]=(f[i&1][j+1][sum][l]+1ll*f[~i&1][j][k][l]*(j+1-l))%mod;
          if(l<2){
            f[i&1][j+1][sum][l+1]=(f[i&1][j+1][sum][l+1]+1ll*f[~i&1][j][k][l]*(2-l))%mod;
            if(j)f[i&1][j][sum][l+1]=(f[i&1][j][sum][l+1]+1ll*f[~i&1][j][k][l]*(2-l))%mod;
          }
          if(j>=1)f[i&1][j][sum][l]=(f[i&1][j][sum][l]+1ll*f[~i&1][j][k][l]*(2*j-l))%mod;
          if(j>=2)f[i&1][j-1][sum][l]=(f[i&1][j-1][sum][l]+1ll*f[~i&1][j][k][l]*(j-1))%mod;
        }
      }
    }
  }
  for(int i=0;i<=m;i++)ans=(ans+f[n&1][1][i][2])%mod;
  return cout<<ans<<'\n',0;
}

CF1515E

考虑按值域插入，维护当前的连续段，只要求这些连续段距离 >1。我们可以任意钦定连续段的距离，转移新增一段、放到一段左右（距离 1 或 2）、合并两个段（距离 2 或 3）。

#include<bits/stdc++.h>
using namespace std;
int n,mod,f[405][405];
struct qmod{
  unsigned long long b,m;
  qmod(unsigned long long mod){
    b=mod,m=(unsigned long long)(((unsigned __int128)1<<64)/b);
  }
  unsigned long long operator()(unsigned long long a){
    unsigned long long q=(unsigned long long)(((unsigned __int128)m*a)>>64),r=a-q*b;
    return r>=b?r-b:r;
  }
}R(2);
int main(){
  f[0][0]=1,cin>>n>>mod,R=qmod(mod);
  for(int i=0;i<n;i++){
    for(int j=0;j<=i;j++){
      f[i+1][j+1]=R(f[i+1][j+1]+1ll*f[i][j]*(j+1));
      if(j>=1)f[i+1][j]=R(f[i+1][j]+1ll*f[i][j]*2*j),f[i+2][j]=R(f[i+2][j]+1ll*f[i][j]*2*j);
      if(j>=2)f[i+2][j-1]=R(f[i+2][j-1]+1ll*f[i][j]*2*(j-1)),f[i+3][j-1]=R(f[i+3][j-1]+1ll*f[i][j]*(j-1));
    }
  }
  return cout<<f[n][1]<<'\n',0;
}

贡献提前/延后计算

在 DP 时，我们需要灵活调整贡献的计算方式，使得通过已有的信息能够推算。若一个位置还没填就已知贡献，就可以直接加上。要达到这一点，我们也可以把贡献拆到时间/决策的每一步上，比如拆成当前还没填的所有元素产生贡献。

我们也可以延后计算，通常见于如果在填的时候统计，后面将无法得知信息，就可以只钦定但不填具体值，到后面合适的时候再填上具体值。

P14364

首先这个过程是从前往后的，很难有其他的顺序，必须直接确定每个人寄没寄。当遇到 s_i=1，我们会有一个形如 c\leq j 的分界线判断这个人寄不寄，且这个分界线是单调递增的。

我们考虑直接把前面选过的分界线下的人数维护出来，这样选择 c\leq j 时就知道方案数。考虑怎么让分界线增加 1，使用贡献延后计算，当我们选择一个 c>j 时，先不分配具体的人，而是当 j 增加 1 时决策之前有几个是 c_i=j+1，这样就可以转移了。具体来说，设 f_{i,j,k} 表示前 i 天寄了 j 个，前 i 天有 k 个人的 c_i\leq j。统计答案时再任意把分界线以上的填好。因为 \sum cnt_i=n，复杂度 O(n^3)。

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,m,cnt[505],sum[505],fac[505],vac[505],f[2][505][505],ans;
char s[505];
int A(int n,int m){
  return n<0||m<0||n<m?0:1ll*fac[n]*vac[n-m]%mod;
}
int C(int n,int m){
  return n<0||m<0||n<m?0:1ll*fac[n]*vac[m]%mod*vac[n-m]%mod;
}
int main(){
  fac[0]=vac[0]=vac[1]=f[0][0][0]=1,cin>>n>>m>>s+1;
  for(int i=2;i<=n;i++)vac[i]=1ll*vac[mod%i]*(mod-mod/i)%mod;
  for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod,vac[i]=1ll*vac[i]*vac[i-1]%mod;
  for(int i=1,c;i<=n;i++)cin>>c,cnt[c]++;
  sum[0]=cnt[0];
  for(int i=1;i<=n;i++)sum[i]=sum[i-1]+cnt[i];
  for(int i=1;i<=n;i++){
    memset(f[i&1],0,sizeof(f[i&1]));
    for(int j=0;j<i;j++){
      for(int k=0;k<=min(i-1,sum[j]);k++){
        if(!f[~i&1][j][k])continue;
        if(s[i]=='1'){
          f[i&1][j][k]=(f[i&1][j][k]+f[~i&1][j][k])%mod;
          for(int l=0;l<=min(cnt[j+1],i-k-1);l++)f[i&1][j+1][k+l+1]=(f[i&1][j+1][k+l+1]+1ll*f[~i&1][j][k]*(sum[j]-k)%mod*C(cnt[j+1],l)%mod*A(i-k-1,l))%mod;
        }
        else{
          for(int l=0;l<=min(cnt[j+1],i-k-1);l++){
            f[i&1][j+1][k+l]=(f[i&1][j+1][k+l]+1ll*f[~i&1][j][k]*C(cnt[j+1],l)%mod*A(i-k-1,l))%mod;
            f[i&1][j+1][k+l+1]=(f[i&1][j+1][k+l+1]+1ll*f[~i&1][j][k]*(sum[j+1]-k-l)%mod*C(cnt[j+1],l)%mod*A(i-k-1,l))%mod;
          }
        }
      }
    }
  }
  for(int i=0;i<=n-m;i++)ans=(ans+1ll*f[n&1][i][sum[i]]*fac[n-sum[i]])%mod;
  return cout<<ans<<'\n',0;
}