DP 杂题选讲

Cute_Wazzy · 2026-07-21 14:22:49 · 算法·理论

dp 状态

CF1025D

注意到 BST 的性质发现可以枚举根，变成了一个经典的区间 dp 的形式，然后记录一下根的位置（这是因为 [l,r] 的根在 l-1 或 r+1）。

:::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define bz __builtin_ctz
int gcd(int a,int b){
    if(a==0)return b;
    if(b==0)return a;
    if(a==b)return a;
    int v1=bz(a),v2=bz(b),d=0;
    int mn=min(v1,v2);
    b>>=v2;while(a){
        a>>=v1;d=b-a;v1=bz(d);
        if(a<b)b=a;a=abs(d);
    }return b<<mn;
}
const int maxn=705;
bool dp[maxn][maxn][2];
bool g[maxn][maxn];
int n,a[maxn];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            g[i][j]=(__gcd(a[i],a[j])>1);
    for(int i=1;i<=n;i++){
        dp[i][i][0]=dp[i][i][1]=1;
    }
    for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            for(int rt=l;rt<r;rt++){
                if(dp[l][rt][0]&&dp[rt+1][r][1]){
                    if(g[r][rt])dp[l][r][0]=1;
                    if(g[rt+1][l])dp[l][r][1]=1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(dp[1][i][1]&&dp[i][n][0]){
            cout<<"Yes";
            return 0;
        }
    }
    cout<<"No";
}

:::

CF1748E

宝宝题。考虑建一个笛卡尔树状物，然后变成了树上计数的问题，定义 f_{u,k} 为 u 权值为 k 的方案树，暴力转移即可。

:::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+5;
const int mod=1e9+7;
int n,m,a[maxn],rt;
int lg[maxn],f[maxn][30];
int s1[maxn],s2[maxn];
int sum1[maxn],sum2[maxn]; 
int qry(int l,int r){
    return max(f[l][lg[r-l+1]],f[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
}vector<vector<int> >dp;
int build(int l,int r){
    if(l>r)return 0;
    int mx=qry(l,r),pos=0;
    for(int i=l;i<=r;i++){
        if(a[i]==mx){
            pos=i;
            if(l==1&&r==n)rt=pos;
            break;
        }
    }int lv=build(l,pos-1),rv=build(pos+1,r);
    s1[pos]=lv;s2[pos]=rv;
    return pos;
}
void dfs(int cur,int fa){
    if(s1[cur])dfs(s1[cur],cur);
    if(s2[cur])dfs(s2[cur],cur);
    if(s1[cur])
        for(int i=1;i<=m;i++)
            sum1[i]=sum1[i-1]+dp[s1[cur]][i],sum1[i]%=mod;
    if(s2[cur])
        for(int i=1;i<=m;i++)
            sum2[i]=sum2[i-1]+dp[s2[cur]][i],sum2[i]%=mod;
    for(int i=1;i<=m;i++){
        if(s1[cur]==0)sum1[i-1]=1;
        if(s2[cur]==0)sum2[i]=1;
        dp[cur][i]+=sum1[i-1]*sum2[i]%mod;
        dp[cur][i]%=mod;
    }sum1[0]=sum2[0]=0;
}
void solve(){
    cin>>n>>m;dp.resize(n+1);
    for(int i=1;i<=n;i++)dp[i].resize(m+1);
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        f[i][0]=a[i];
    for(int i=1;i<=lg[n];i++)
        for(int j=1;j<=n-(1<<i)+1;j++)
            f[j][i]=max(f[j][i-1],f[j+(1<<(i-1))][i-1]);
    for(int i=1;i<=n;i++)s1[i]=s2[i]=0;
    build(1,n);dfs(rt,0);
    int ans=0;
    for(int i=1;i<=m;i++)ans+=dp[rt][i],ans%=mod;
    cout<<ans<<"\n";
    for(int i=1;i<=n;i++)dp[i].clear();
}
signed main(){
    lg[1]=0;
    for(int i=2;i<maxn;i++)
        lg[i]=lg[i>>1]+1;
    int t;cin>>t;
    while(t--)solve();
}

:::

CF1767C

难点在于设计状态。发现只需要当前下标和后缀极大连续段长度状物即可刻画一个状态。

维护一下长度上下界，直接转移就行了。

:::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=105;
const int mod=998244353;
int a[maxn][maxn];
int dp[maxn][maxn];
int L[maxn],R[maxn];
signed main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=-1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n-i+1;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++){
        //枚举第 i 位的上下界
        R[i]=i,L[i]=1;
        for(int j=1;j<=i;j++){
            if(a[j][i-j+1]==1)R[i]=min(R[i],j);
            if(a[j][i-j+1]==2)L[i]=max(L[i],j+1);
        }
        if(L[i]>R[i]){cout<<"0";return 0;}
    }dp[1][1]=2;
    for(int i=2;i<=n;i++){
        for(int j=L[i];j<=R[i];j++){
            dp[i][j]+=dp[i-1][j];
            dp[i][j]%=mod;
            if(j==i){
                int tot=0;
                for(int k=L[i-1];k<=R[i-1];k++)
                    tot=(tot+dp[i-1][k])%mod;
                dp[i][j]+=tot;
                dp[i][j]%=mod; 
            }
        }
    }int res=0;
    for(int i=1;i<=n;i++)res=(res+dp[n][i])%mod;
    cout<<res;
}

:::

CF2109E

意味题，秒了。

发现正着做需要维护后面的翻转次数状物，发现不好做。

考虑倒着做，而且具体后面的翻转方案不在意，用组合数转移即可。

:::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=505;
const int mod=998244353;
int fac[maxn],inv[maxn];
int N=maxn-5;
int n,k;string s;
int dp[maxn][maxn];
int qpow(int a,int b){
    int res=1;while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;b>>=1;
    }return res;
}void chk(int&a,int b){
    a=(a+b%mod)%mod;
}int cal(int x,int y){
    if(x>y)return 0;
    return fac[y]*inv[x]%mod*inv[y-x]%mod;
}void solve(){
    cin>>n>>k>>s;
    for(int i=1;i<=n+1;i++)
        for(int j=0;j<=k+1;j++)
            dp[i][j]=0;
    s=" "+s;dp[n+1][0]=1;
    for(int i=n+1;i>=2;i--){
        for(int j=0;j<=k;j++){
            for(int l=0;l<=k-j;l++){
                if(s[i-1]=='0')chk(dp[i-1][j+l],dp[i][j]*cal(l,(j+l+1)/2));
                else chk(dp[i-1][j+l],dp[i][j]*cal(l,(l+j)/2));
            }
        }
    }cout<<dp[1][k]<<"\n";
}
signed main(){
    fac[0]=1;
    for(int i=1;i<=N;i++)
        fac[i]=fac[i-1]*i%mod;
    inv[N]=qpow(fac[N],mod-2);
    for(int i=N;i>=1;i--)
        inv[i-1]=inv[i]*i%mod;
    int t;cin>>t;while(t--)
    solve();return 0;
}

:::

CF1110D

意味题。发现顺子同样的最多用 3 次，从小到大 dp 即可，记录一下附近的顺子用了几个即可，细节还好。

:::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+5;
int a[maxn],dp[maxn][4][4];
unordered_map<int,int>vis; 
signed main(){
    int n,m;cin>>n>>m;
    vector<int>num;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        vis[a[i]]++;
        if(vis[a[i]]==1)
            num.push_back(a[i]);
    }sort(num.begin(),num.end());
    for(int i=1;i<=m;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                for(int t=0;t<3;t++){
                    if(vis[i]<j+k+t)continue;
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][t]+((vis[i]-j-k-t)/3+j));
                }
            }
        }
    }cout<<dp[m][0][0];
}

:::

CF1699D

好题？首先考虑可以用众数出现次数来刻画一个区间是否可以删除，这个直接做是 O(n^2) 的。

然后定义 dp_i 前缀 1\sim i 保留 i 最多能保留几个。

细节是简单的，直接转移就行了。

:::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e3+5;
int flag[maxn][maxn];
int n,a[maxn],dp[maxn];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)flag[i][j]=0;
    for(int i=1;i<=n;i++)dp[i]=0;
    for(int i=1;i<=n;i++){
        int vis[n+1]={};
        int mx=0,num=-1;
        for(int j=i;j<=n;j++){
            vis[a[j]]++;
            if(vis[a[j]]>mx){
                mx=vis[a[j]];
                num=a[j];
            }
            if((j-i)%2&&mx*2<=(j-i+1))flag[i][j]=1;
        }
    }
    /*
1
6
1 1 1 2 2 2
    */
//  for(int i=1;i<=n;i++){
//      for(int j=i;j<=n;j++)
//          cout<<flag[i][j]<<" ";
//      cout<<"\n";
//  }
    for(int i=1;i<=n;i++){
        //考虑 dp i
        if(flag[1][i-1]||i==1)dp[i]=1;
        //枚举上一个
        for(int j=1;j<i;j++){
            if(a[j]==a[i]&&(flag[j+1][i-1]||(j==i-1))&&dp[j])dp[i]=max(dp[i],dp[j]+1);
        } 
    }int res=0;
    for(int i=1;i<=n;i++){
        if(flag[i+1][n]||i==n)res=max(res,dp[i]);
    }cout<<res<<"\n";
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;cin>>t;while(t--)solve();
}

:::

CF1336C

什么叫 *2200 是黄。

发现这个形式是典型的区间 dp，然后拼前缀可以看作是区间的对应，然后直接做 dp 就行了。

但是这个只能计算 |S|=|T| 时。 其他时候考虑在 T 结尾放通配符即可。

:::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=3e3+5;
const int mod=998244353;
string s,t;
void chk(int&a,int b){a=(a+b%mod)%mod;}
int f[maxn][maxn];
signed main(){
    cin>>s>>t;int n=s.size();
    int oldlen1=s.size();
    int oldlen2=t.size();
    if(t.size()<n){
        while(t.size()<n){
            t=t+"*";
        }
    }
    s=" "+s;t=" "+t;
//  cout<<s<<"\n"<<t<<"\n";
    for(int i=1;i<=n;i++)
        f[i][i]=(s[1]==t[i]||t[i]=='*')*2;
    for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            int t1=(s[r-l+1]==t[l]||t[l]=='*');
            int t2=(s[r-l+1]==t[r]||t[r]=='*');
            if(t1)chk(f[l][r],f[l+1][r]);
            if(t2)chk(f[l][r],f[l][r-1]);
        }
    }int ans=0;
    for(int i=oldlen2;i<=oldlen1;i++)chk(ans,f[1][i]);
    cout<<ans;
}

:::

CF1987F1

确实有趣。

第一步发现没啥可以直接做的 dp 方法，考虑区间 dp。

然后考虑定义 dp_{l,r} 为全部删除 [l,r]，1\sim l-1 至少得删除多少个东西。

你发现转移的形式和括号匹配是类似的。要么是套一层在外面，这个时候只要先删 l+1\sim r-1 再删 a_l 就行了，删除是随时可以进行的，判断一下就行了。要么是并列的，此时枚举分割点就行了，注意，dp_{k+1,r} 此时的价值要减去 (k-l+1)。

做完这个之后做一个一维的 dp，O(n^2) 转移即可。

:::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=105;
int n,a[maxn],dp[maxn][maxn],f[maxn];
void chk(int&a,int b){a=max(a,b);}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dp[i][j]=1e9;
    for(int i=1;i<=n+1;i++)f[i]=0;
    for(int i=1;i<=n;i++)dp[i+1][i]=0;
    for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            if(l%2==a[l]%2&&l>=a[l]&&dp[l+1][r-1]<=l-a[l])dp[l][r]=l-a[l];
            for(int k=l+1;k<r-1;k+=2){
                dp[l][r]=min(dp[l][r],max(dp[l][k],dp[k+1][r]-(k-l+1)));
            }
        }
    }for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j+=2){
            if(f[i]>=dp[i][j])f[j+1]=max(f[j+1],f[i]+(j-i+1));
        }f[i+1]=max(f[i],f[i+1]);
    }cout<<f[n+1]/2<<"\n"; 
}signed main(){
    int t;cin>>t;while(t--)solve();
}

:::

AT_arc178_d

不错的题。

首先发现 x 能删掉的条件不难刻画，即比 x 小的数都在它的一边。

之后你考虑原序列得是这个的子序列。你如果直接做 dp 的话，发现状态不好刻画。所以换一个角度，即在原序列中插入，做区间 dp 状物。为了确定状态，定义 dp_{l,r,x} 为 l\sim r 中恰好插了 x 的方案数。

先枚举 x，然后对 x 是否要被删进行分讨。

发现要删除的时候要做一个求和，这个东西前缀和优化是简单的。

:::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=505;
const int mod=998244353;
int n,m,a[maxn],f[maxn][maxn][maxn];
unordered_map<int,int>vis;
unordered_map<int,int>pos;
void chk(int&a,int b){a=(a+b%mod)%mod;}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>a[i];
    for(int i=1;i<=m;i++)vis[a[i]]++;
    for(int i=1;i<=m;i++)pos[a[i]]=i;
    if(vis[0]){f[pos[0]][pos[0]+1][0]=1;}
    else{for(int l=1;l<=m+1;l++)f[l][l][0]=1;}
    for(int x=1;x<n;x++){
        if(vis[x]){
            int p=pos[x];
            for(int l=1;l<=m+1;l++){
                for(int r=l;r<=m+1;r++){
                    chk(f[min(p,l)][max(p+1,r)][x],f[l][r][x-1]);
                }
            }
        }else{
            int sum1=0,sum2=0;
            for(int r=1;r<=m+1;r++){
                sum1=0;
                for(int l=r;l;l--)
                    chk(sum1,f[l][r][x-1]),chk(f[l][r][x],sum1);
            }
            for(int l=1;l<=m+1;l++){
                sum2=0;
                for(int r=l;r<=m+1;r++){
                    chk(sum2,f[l][r][x-1]),chk(f[l][r][x],sum2);
                }
            }
        }
    }cout<<f[1][m+1][n-1];
}

:::

AT_abc250_e

考虑集合 hash，发现可以直接去重后随机标数然后前缀异或，就做完了。

CF1175F

好题。

首先注意到这种子序列必须恰好包含一个 1，可以直接扫一遍。

维护当前的指针 pos 和最大值 mx，那么只有可能是 [pos-mx+1,pos] 是满足条件的序列。

考虑怎么去判断，因为不关注顺序直接异或 hash 就做完了。

:::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e5+5;
const int mod=14897394578;
int n,a[maxn];
int ans=0;unordered_map<int,int>mp;
map<pair<int,int>,int>vis;
int val[maxn],sum[maxn];
int len;
void solve(){
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]^mp[a[i]];
    int pos=1;while(a[pos]!=1&&pos<=n)pos++;
    while(pos<=n){
        int mx=a[pos];
        while(a[++pos]!=1&&pos<=n){
            mx=max(mx,a[pos]);
            if(pos>=mx&&(sum[pos]^sum[pos-mx])==val[mx])ans++;
        }
    }
}
signed main(){
    cin>>n;mt19937_64 rng(time(0));
    for(int i=1;i<=n;i++)cin>>a[i],ans+=(a[i]==1);
    for(int i=1;i<=n;i++){
        int val=rng();
        while(!val)val=rng();
        val=abs(val);
//      assert(val>0);
        if(!mp[a[i]])mp[a[i]]=val;
    }
    for(int i=1;i<=n;i++){
        if(mp[i])val[i]=val[i-1]^mp[i];
        else{for(int j=i;j<=n;j++)val[j]=-1;break;}
    }
    solve();reverse(a+1,a+n+1);
    solve();cout<<ans;
}

:::

CF1746F

独立切了。发现给的判定条件不可做，考虑用一种随机而且容易维护的东西大概的去刻画它。

发现可以直接给每个随机赋值，一个区间合法时一定有其权值和是 k 的倍数。容易分析出错误的概率是 \frac{1}{k}，开一些树状数组就可以轻松维护。

难调，常数写大了过不了 /fn。

dp 优化

P11333

适合用来复习。教练声称这个题适合放 NOIP T2 /fn。

考虑简单的写出 dp 方程，定义 f_i 为处理 1\sim i 后的最小答案。

差分之后转移就变成了区间平移和区间加，显然这个东西 fhq-treap 可以维护。

笑点解析：为了这道题我复习了 2h 的 treap，然后发现用的是 fhq-treap。

代码懒得写了。

CF1093F & P14599

难死了。

考虑 CF1093F 怎么做，首先有一个容易的 dp，定义 dp_{i,j,k} 表示考虑完第 i 个元素，填的颜色是 j，目前极长同颜色段的长度是 k。

我们发现我们只关心让它的长度小于 len，具体长度不关心。

考虑 dp_{i,j} 状态意义同上。

没有约束的时候转移是简单的，考虑在没有约束的基础上去除第一次不合法的情况，这个也是简单的。

:::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+5;
const int maxk=105;
const int mod=998244353;
int dp[maxn][maxk];//第 i 位填 j 的方案数 
int a[maxn],sum[maxn][maxk];
int cnt[maxn];
//sum i j 前 i 位 j 的数量 k+1 为 -1 
int n,k,len;
int qry(int l,int r,int v){
    return sum[r][v]-sum[l-1][v];
}
void solve(){
    cin>>n>>k>>len;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            if(a[i]==j)sum[i][a[i]]=sum[i-1][a[i]]+1;
            else sum[i][j]=sum[i-1][j];
        }sum[i][k+1]=sum[i-1][k+1]+(a[i]==-1);
    }
//  for(int j=1;j<=k+1;j++){
//      for(int i=1;i<=n;i++)cout<<sum[i][j]<<" ";
//      cout<<"\n"; 
//  }
    if(len==1){cout<<"0";return;}
    for(int j=1;j<=k;j++){
        if(a[1]==-1)dp[1][j]=1;
        else dp[1][a[1]]=1;
        cnt[1]+=dp[1][j];
    }cnt[0]=1;
    for(int i=2;i<=n;i++){
        int tot=0;
        for(int j=1;j<=k;j++){
            if(a[i]!=j&&a[i]!=-1)continue;
            int los=0;
            int lst=cnt[i-1],l=i-len+1,r=i;
            if(l<=0){
                dp[i][j]=cnt[i-1];
                tot+=cnt[i-1];tot%=mod;
                continue;
            }
            int v1=qry(l,r,k+1);
            int v2=qry(l,r,j);
            //真唐，你已经钦定 a_i=j 
            //如果非法只能是 a_i-len+1~a_i 全部都是 j 
            //dp i-len c c 不为这个
            //c=1~k dp[i][j]-=(cnt[i-len]-dp[i-len][c];
            if(v1+v2==len){los=1;}
            //dp i j=dp i-1 c-unfa
            //dp i j=dp i-1 c-[can] dp[i-len][c]
            //对于每个 dp i j 记录 sum dp i c
            //其中 c 是 a_i 可以取到的值
            dp[i][j]=cnt[i-1]-cnt[i-len]*los%mod+dp[i-len][j]*los%mod;
            dp[i][j]%=mod;dp[i][j]+=mod;
            dp[i][j]%=mod;tot+=dp[i][j];tot%=mod;
        }cnt[i]=tot;
    }int ans=0;
    for(int i=1;i<=k;i++){
        ans+=dp[n][i];
        ans%=mod;
    }cout<<ans;
}
signed main(){
    int t=1;while(t--)solve();
}//sbdev

:::

注释是瞎写的，考虑 P14599 在 CF1093F 原做法上的优化。

这个式子不能套 DS，就只能考虑压缩状态。

定义 f_i 是前 i 个数的合法方案数，nxt_i 是 i 右侧第 1 个确定的数，g_i 为 a_i=-1 的情况下，强制让 i 填入 nxt_i 的方案数。

接下来考虑位置 i，[i-len+1,i] 都可以变成 C 时需要容斥掉的方案数。