[P16350] 「Gensokyo OI Round 1」隙间插曲 题解

· · 题解

删开头是简便的，视为删除一个前缀即可，但是删结尾可能会出现跳跃的情况，比较麻烦。但可以发现，如果倒序操作，可以将删除结尾视作积累一个删除势能，在势能降为 0 之前，遍历到的数都要被删除。

于是可以将势能加入状态，倒序 dp。设 f_{i,j,k} 表示从第 n 次操作考虑到第 i 次，当前删除势能为 j，需要删除的前缀长度为 k，此时删除的 a_i 总和最小值。分类讨论 a_i 是否等于 0。

总复杂度 \mathcal{O}(n^3)，看起来过不了，但实际上，若 i\sim n 一共有 c_i 个 a_x=0，那么实际上对 f_{i,j,k} 而言 j+k\le c_i，则有效状态数约为 \frac 12\sum c_i^2，最坏情况为 a_i 均为 0，直接求和可粗略估计得有至少 \frac 16 常数，加上两秒时限显然可过。

:::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef double db;
const ll maxn=1007,ee=1e18,p=1e9+7;
ll n,a[maxn],m,b[maxn],d[maxn],val[maxn],f[maxn][maxn],ans,tot;
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0);
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>a[i],tot+=a[i],d[i]=d[i-1];
        if(a[i]) b[++m]=a[i],d[i]++;
        else d[i]--;
    }
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    ll c=0;
    for(ll i=n;i>=1;i--){
        if(a[i]==0){
            c++;
            for(ll j=c;j>=0;j--)for(ll k=c-j;k>=0;k--){
                f[j][k]=min(j?f[j-1][k]:ee,k?f[j][k-1]:ee);
                if(d[i]<k){
                    if(j) f[j][k]=ee;
                    else f[j][k]=(k?f[j][k-1]:ee);
                }
            }
        }else{
            for(ll j=0;j<=c;j++)for(ll k=c-j;k>=0;k--){
                if(j) f[j][k]=f[j+1][k]+a[i];
                else f[j][k]=min(f[j][k],f[j+1][k]+a[i]);
            }
        }
    }
    for(ll i=0,s=0;i<=m;i++){
        ans=max(ans,tot-f[0][i]-s),s+=b[i+1];
    }
    cout<<ans<<"\n";
    return 0;
}

:::