题解：CF1987F2 Interesting Problem (Hard Version)

· · 题解

@DaiRuiChen007 无敌了！

唐氏区间 dp 拖了一年。

首先按照区间 dp 的基本思路：设 dp_{l,r} 代表 [l,r] 区间的答案。考虑到我们要通过删除前面的数给删除后面的数机会，不妨设 dp_{l,r} 代表删除完 [l,r] 在 [1,l-1] 要至少删除多少个数。

区间 dp 的两种常见转移方式，一种是 dp_{l,r} 从 dp_{l+1,r-1} 转移而来，另外一种是枚举中间断点，从 dp_{l,mid} 和 dp_{mid+1,r} 转移而来。

第一种转移在本题当中，可以看 (l,r) 这对数的删除转移情况，因为是先把 [l+1,r-1] 删完了，所以 (l,r) 在前面删的数的数量必须大于等于 [l+1,r-1]。

第二种转移直接枚举断点，并排删除 dp_{l,mid} 和 dp_{mid+1,r}，注意删除 [l,mid] 时候给 [mid+1,r] 的删除带来的影响。

最后用 f_i 转移判断能删多少个数：如果 dp_{\left \{ j|1\le j\le i-1 \right \} ,i}（要求 [j,i] 长度为偶）的值小于等于 f_{j-1}，就可以直接删除 [j,i] 转移而来。

时间复杂度 O(n^3)，O(n^4) 是什么做法呢？

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
    int a=0,b=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  b=-1;
        c=getchar();
    }
    while(isdigit(c)){
        a=(a<<1)+(a<<3)+(c-'0');
        c=getchar();
    }
    return a*b;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10)   write(x/10);
    putchar(x%10+48); 
}
inline void write1(int x){
    write(x),putchar(' ');
}
inline void write2(int x){
    write(x),putchar('\n');
}
int n;
int a[817]; 
int dp[817][817];   //dp[i][j] 代表消除完 [i,j] 至少要消除前面多少个数 
int dp1[817];   //dp1[i] 代表最少保留前 i 个数的几个 
//更新：最多删多少个  
void solve(){
    n=read();
    for(int i=1;i<=800;i++){
        for(int j=1;j<=800;j++){
            dp[i][j]=1e18;
        } 
    } 
    for(int i=1;i<=n;i++){
        a[i]=read();
        dp[i][i-1]=0;
        dp1[i]=0; 
    }
    for(int k=2;k<=n;k+=2){
        for(int l=1,r=l+k-1;r<=n;l++,r++){
            //现在转移的是 [l,r] 区间 
            if(l>=a[l]&&(l-a[l])%2==0){
                int now=l-a[l];
                if(dp[l+1][r-1]<=now)   dp[l][r]=now;
            } 
            for(int i=l+1;i<=r;i+=2){
                //dp[l][i] 和 dp[i+1][r] 的连接 
                dp[l][r]=min(dp[l][r],max(dp[l][i],dp[i+1][r]-(i-l+1))); 
            }
//          cout<<'#'<<l<<' '<<r<<' '<<dp[l][r]<<endl;
        }
    }
//  putchar('\n');
    dp1[0]=0;
    for(int i=1;i<=n;i++){
        dp1[i]=dp1[i-1];
//      dp1[i]=dp1[i-1]+1;  //第一种转移方案 
        for(int j=i-1;j>=1;j-=2){
            if(dp1[j-1]>=dp[j][i]){
                dp1[i]=max(dp1[i],dp1[j-1]+(i-j+1));
//              cout<<'!'<<i<<' '<<j<<' '<<dp1[j-1]+(i-j+1)<<endl;
            }
        } 
    }
    write2(dp1[n]/2);
    return;
}
signed main(){
    int T=read();
    while(T--)  solve();
    return 0;
}//一定要挽回罗琪钧的遗憾啊，一定会挽回罗琪钧的遗憾的。