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

· · 题解

神秘 dp，蓝？

注意到既可以在开头删又可以在结尾删比较麻烦。但因为最终序列中的元素个数 x 是确定的（等于非零元素个数减去零元素个数），所以考虑变换问题为：删除操作可以选择删掉结尾元素或者什么都不做，最大化剩余序列的最后 x 个元素之和。

考虑倒推。设 m 为非零元素个数，dp_{i,j} 为保留第 [i,m] 个非零元素中的恰好 j 个数，可以得到的最大和，其中 0\le j\le x。

显然 dp_{m+1,0}=0，对于其他 j，dp_{m+1,j}=-\infty。我们需要求的就是 \max_{1\le i\le m}dp_{i,x}。

对于 dp_{i,j}，我们有两种处理方式：

一种是保留它，此时得到的值为 dp_{i+1,j-1}+b_i，其中 b_i 表示第 i 个非零元素。

另一种是删除它。注意到每个元素被删除都需要且仅需要它右边直到某个元素全部被删除，设这是第 c_i 个元素，则此时获得的值为 dp_{c_i+1,j}。

所以剩下的问题就是 c_i 怎么求。考虑遍历 a 数组，遍历的同时求出 a 的当前前缀对应的 b 与 c。也就是说，我们需要确定当 a 的末尾新加入一个元素时，b 和 c 如何变化。

如果这个元素非零，则 b 也在末尾加入这一元素，c 不变。

否则，考虑原先最右边一个到目前为止还不可能被删除的元素（代码中用 c 值为 0 表示）。该元素如果需要被删除，则需要右边的元素全部被删除，这样新加入的删除操作才能作用于它。所以该元素的 c 值变为当前的 m，其他元素的 c 不变。

这次遍历可以与输入同时进行，完成后即可开始刚才的 dp。

总时间复杂度 O(n^2)，常数很小，可以（在八毫秒以内）通过。 ::::success[AC 代码]

#include <iostream>
using namespace std;
int b[1001],c[1001];
long long dp[1002][1001];
int main() {
    int n,m=0,x=0,a,i,j;
    long long ans=0;
    cin>>n;
    for(i=1;i<=n;i++) {
        cin>>a;
        if(a) b[++m]=a;else {x++;for(j=m;j&&c[j];j--);c[j]=m;}
    }
    x=m-x;
    for(j=1;j<=x;j++) dp[m+1][j]=-1e18;
    for(i=m;i;i--) {
        dp[i][0]=-1e18;for(j=1;j<=x;j++) dp[i][j]=dp[i+1][j-1]+b[i];
        if(c[i]) for(j=0;j<=x;j++) dp[i][j]=max(dp[i][j],dp[c[i]+1][j]);
        ans=max(ans,dp[i][x]);
    }
    cout<<ans;
    return 0;
}

:::: AC 记录。 ::::info[闲话] 感谢善良的出题人放的 subtask 3 拯救了我的分数。 ::::