区间DP 学习笔记

xujindong_ · 2025-11-20 22:43:05 · 个人记录

概述

区间 DP 是 DP 状态是一段区间的信息的 DP。这种问题，可能子状态是天然的一段区间。更多的时候问题涉及合并或分裂。一个元素由原序列的一段区间的元素合并而成，我们可以考虑当前区间由哪些段合并而成。或者在区间内取一些特殊元素，分成若干区间，这些区间是比较独立的子问题。一种特殊情况是笛卡尔树式的 DP，取区间内最大/最小/最早/最晚的元素，分成两边独立的区间。

状态通常是 f_{l,r}，也有时使用值域定义域互换，变成 g_{l,k}/g_{r,k} 表示最右的 r/最左的 l 使 f_{l,r}=k。枚举顺序也有两种：先枚举区间长再枚举区间，或者倒序枚举 l 再正序枚举 r。后者不完全按区间长枚举，但仍然保证区间包含顺序，且一次性处理完一个 l。

例题

P9523

显然我们只会打出 S 的子串，设 f_{l,r} 为打出 S[l,r] 的最小代价。操作 A 的转移 f_{l,r}\gets\min(f_{l,r-1},f_{l+1,r})+A。操作 C 的转移是找到一个子串 S[x,y]，钦定它是 S[l,r] 的 border（否则可以用操作 A 转移），若 S[x,y] 在 S[l,r] 不交地出现了 k 次，则 f_{l,r}\gets f_{x,y}+B+kC+(r-l+1-k(y-x+1))A。刷表法转移更容易，每次找到 S[x,y] 的下一个出现即可。而且因为不交出现只有 \frac n{len} 次，复杂度 O(n^2\log n)。求下一次出现可以先递推两两后缀的 LCP，枚举 l 和下一次出现的左端点 l'，更新所有 r\leq\min(l+lcp(l,l')-1,l'-1)。

#include<bits/stdc++.h>
using namespace std;
int n,l[2505][2505],nxt[2505][2505];
long long f[2505][2505],a,b,c;
char s[2505];
int main(){
  memset(f,0x3f,sizeof(f)),cin>>n>>s+1>>a>>b>>c;
  for(int i=n;i>=1;i--)for(int j=n;j>=i;j--)l[i][j]=s[i]==s[j]?l[i+1][j+1]+1:0;
  for(int i=1;i<=n;i++)for(int j=i+1,k=i;j<=n;j++)while(k<min(j,i+l[i][j]))nxt[i][k]=j+k-i,k++;
  for(int len=1;len<=n;len++){
    for(int l=1,r=len;r<=n;l++,r++){
      f[l][r]=l==r?a:min(f[l][r],min(f[l+1][r],f[l][r-1])+a);
      for(int i=nxt[l][r],j=2;i;i=nxt[i-len+1][i],j++)f[l][i]=min(f[l][i],f[l][r]+b+j*c+(i-l+1-j*len)*a);
    }
  }
  return cout<<f[1][n]<<'\n',0;
}

AT_arc108_e

核心观察是对于一个区间 [l,r]，l,r 被选上但中间的点还未选，在这个区间内每个数是否合法和外面无关。也就是说，每个合法的数作为这个区间内下一个被选的数的概率相同，且这又会将这个区间分为两个子问题。区间 DP f_{l,r} 表示 l,r 被选后区间 [l,r] 期望还能选几个，g_{l,r}=\sum_{i=l+1}^{r-1}[a_l<a_i<a_r]，则 f_{l,r}=\frac{\sum_{i=l+1}^{r-1}(f_{l,i}+f_{i,r})[a_l<a_i<a_r]}{g_{l,r}}+1。发现我们可以用 BIT 维护 \sum f_{l,i},\sum f_{i,r} 和 g，区间 DP 的过程恰好处理掉了下标的限制。O(n^2\log n)。

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int n,a[2005],inv[2005],f[2005][2005];
template<typename T,int maxn>struct BIT{
  int tr[maxn];
  void add(int x,int k){
    for(;x<=n;x+=x&-x)tr[x]=(tr[x]+k)%mod;
  }
  int query(int x,int ans=0){
    for(;x;x-=x&-x)ans=(ans+tr[x])%mod;
    return ans;
  }
};
BIT<int,2005>g[2005],fl[2005],fr[2005];
int main(){
  inv[0]=inv[1]=1,cin>>n,n+=2;
  for(int i=2;i<=n;i++)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
  for(int i=2;i<n;i++)cin>>a[i],a[i]++;
  a[1]=1,a[n]=n;
  for(int i=1;i<n;i++)g[i].add(a[i+1],1);
  for(int len=3;len<=n+2;len++){
    for(int l=1,r=len;r<=n;l++,r++){
      int cnt=g[l].query(a[r])-g[l].query(a[l]-1);
      if(a[l]<a[r]&&cnt)f[l][r]=(1ll*((fl[l].query(a[r])-fl[l].query(a[l]-1)+fr[r].query(a[r])-fr[r].query(a[l]-1))%mod+mod)*inv[cnt]+1)%mod;
      g[l].add(a[r],1),fl[l].add(a[r],f[l][r]),fr[r].add(a[l],f[l][r]);
    }
  }
  return cout<<f[1][n]<<'\n',0;
}

P4563

对于区间 [l,r]，r 必选。观察性质，r 能看到的所有点会将区间分成若干段，则每段不能看到另一段里的点。

证明：设 a<b<c<r 且 r 能看到 b，c 能看到 a 且 r 不能看到 a,c，则点 a,c 都低于 b,r 的连线，因此 a,c 的连线会被 b 挡住。

考虑区间 DP，枚举右端点，左端点不断向左扩展。在扩展的过程中可以直接维护出右端点能看到的点分成的段。设相邻两分界点为 l',r'，中间的段是一个子问题，只能由 r'-1,r' 看到，代价 \min(f_{l'+1,r'-1},f_{l'+1,r'-1})。维护一下最后一个分界点与目前完整的段的和即可。

#include<bits/stdc++.h>
using namespace std;
int n,h[5005],f[5005][5005],ans;
int main(){
  cin>>n;
  for(int i=1;i<=n;i++)cin>>h[i];
  for(int i=1;i<=n;i++){
    f[i][i]=1,ans^=1;
    int sum=1,l=0;
    for(int j=i-1;j>=1;j--){
      if(!l||1ll*(h[i]-h[j])*(i-l)<1ll*(h[i]-h[l])*(i-j))sum+=l?min(f[j+1][l],f[j+1][l-1]):0,l=j;
      f[j][i]=min(f[j][l],f[j][l-1])+sum,ans^=f[j][i];
    }
  }
  return cout<<ans<<'\n',0;
}

QOJ8089

首先有个区间 DP，因为第一次之后分割点总是 l-1 或 r+1，可以 DP f_{l,r},g_{l,r}。

注意到直接二分答案不超过 5\log n，事实上答案 \leq42。应用经典技巧，值域定义域互换，f_{x,l} 表示 x 次，显示器是 l-1，左端点 l 能解决的最大 r。g 同理，下面只分析一边。转移为 f_{x,l}=\max_{g_{x-w(l-1,p)-1,p-1}\leq l}f_{x-w(l-1,p),p+1}。

对于每一层 x，扫描线，枚举 p,d=w(l-1,p)-1，把二元组 (p,d) 挂到 g_{x-w(l-1,p)-1,p-1} 上。从左往右枚举，对于这个代价 w，我们可以看成两个数各自把某些位变成 -1 后相等。枚举变化位的集合 S，|S|=d-1，用 f_{x-w(l-1,p),p+1} 更新一个 w_{tr_{p,S},S}，tr_{p,S} 为 p 将 S 的位改为 -1 的结果。最后用 w_{tr_{l-1,S},S} 更新 f_{x,l}。此部分复杂度 O(2^drn)(d=5,r=42)。

查询时，枚举第一次问 p，二分左右问的次数，O(Tn\log r)。

#include<bits/stdc++.h>
using namespace std;
int t,l,r,tr[100005][32],f[47][100005],g[47][100005],w[32][161056];
vector<int>s[6];
vector<pair<int,int> >e[100005];
int main(){
  memset(g,0x3f,sizeof(g));
  for(int i=0;i<32;i++)s[__builtin_popcount(i)].push_back(i);
  for(int i=0;i<=100000;i++)for(int j=0;j<32;j++)for(int k=0,p=1,now=i;k<5;k++,p*=11,now/=10)tr[i][j]+=p*(j>>k&1?10:now%10);
  for(int i=1;i<=99999;i++)f[0][i]=g[0][i]=i;
  for(int x=0;x<=42;x++)g[x][0]=1,f[x][100000]=99999;
  for(int x=1;x<=42;x++){
    for(int i=1;i<=99999;i++)e[i].clear();
    for(int i=0;i<32;i++)for(int j=0;j<=161051;j++)w[i][j]=0;
    for(int i=1;i<=99999;i++)for(int d=1;d<=min(6,x);d++)e[g[x-d][i-1]].push_back(make_pair(i,d));
    for(int i=1;i<=99999;i++){
      for(int j=0;j<e[i].size();j++){
        int p=e[i][j].first,d=e[i][j].second;
        for(int k=0;k<s[d-1].size();k++){
          int mask=s[d-1][k];
          w[mask][tr[p][mask]]=max(w[mask][tr[p][mask]],f[x-d][p+1]);
        }
      }
      for(int mask=0;mask<32;mask++)f[x][i]=max(f[x][i],w[mask][tr[i-1][mask]]);
    }
    for(int i=1;i<=99999;i++)e[i].clear();
    for(int i=0;i<32;i++)for(int j=0;j<=161051;j++)w[i][j]=100000;
    for(int i=1;i<=99999;i++)for(int d=1;d<=min(6,x);d++)e[f[x-d][i+1]].push_back(make_pair(i,d));
    for(int i=99999;i>=1;i--){
      for(int j=0;j<e[i].size();j++){
        int p=e[i][j].first,d=e[i][j].second;
        for(int k=0;k<s[d-1].size();k++){
          int mask=s[d-1][k];
          w[mask][tr[p][mask]]=min(w[mask][tr[p][mask]],g[x-d][p-1]);
        }
      }
      for(int mask=0;mask<32;mask++)g[x][i]=min(g[x][i],w[mask][tr[i+1][mask]]);
    }
  }
  cin>>t;
  while(t--){
    cin>>l>>r;
    int ans=0x3f3f3f3f;
    for(int i=l;i<=r;i++){
      int l1=0,r1=42,l2=0,r2=42;
      while(l1<r1){
        int mid=(l1+r1)>>1;
        if(g[mid][i-1]<=l)r1=mid;
        else l1=mid+1;
      }
      while(l2<r2){
        int mid=(l2+r2)>>1;
        if(f[mid][i+1]>=r)r2=mid;
        else l2=mid+1;
      }
      int now=max(l1,l2);
      for(int j=i;j;j/=10)if(j%10)now++;
      ans=min(ans,now+1);
    }
    cout<<ans<<'\n';
  }
  return 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;
}