P16350 隙间插曲题解

Mier_Samuelle · 2026-04-25 20:07:56 · 题解

rk 32，要上大分了 /se

记加数操作共 a 次，删数操作共 b 次，则最终剩下 m=a-b 个数。

观察操作的性质。容易发现，删队尾总是会删掉左侧最近的一个还未删除的数，而通过删队首删除的数一定构成了序列的一个前缀。这启示我们倒着做。在倒序遍历的过程中，我们每遇到一个 0，若选择删队尾，就累积一次删除操作，并在下次遇到非 0 数时执行操作。若遇到非 0 数时，没有需要执行的删除操作，则该数保留。

据此，我们定义 f_{i,j,k} 为：处理到第 i 个数，累积了 j 次删数操作，且已保留 k 个数的最大和。则转移为：

若 a_i=0，则可以选择：
- 删队首，f_{i,j,k} \rightarrow f_{i-1,j,k}。
- 删队尾，f_{i,j,k} \rightarrow f_{i-1,j+1,k}。
若 a_i>0，则：
- 若 j>0，则需要执行删除操作，f_{i,j,k} \rightarrow f_{i-1,j-1,k}。
- 若 j=0，则不需要执行删除操作，此时：
  - 若 k<m，则该数保留，f_{i,j,k}+a_i \rightarrow f_{i-1,j,k+1}。
  - 若 k=m，则该数一定会作为队首被删掉，f_{i,j,k} \rightarrow f_{i-1,j,k}。

可用滚动数组滚掉一维，空间复杂度 O(n^2)，时间复杂度 O(n^3)，常数小，可以通过。

:::success[实现]{open}

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1010;
int a[MAXN], f[MAXN][MAXN], g[MAXN][MAXN];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int cntp = 0, cntd = 0;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        if (a[i]){
            cntp++;
        }
        else{
            cntd++;
        }
    }
    memset(f, -1, sizeof(f));
    f[0][0] = 0;
    int cntr = cntp - cntd;
    int nowp = 0, nowd = 0;
    for (int i = n; i >= 1; i--){
        for (int j = 0; j <= nowd + 1; j++){
            for (int k = 0; k <= min(cntr, nowp + 1); k++){
                g[j][k] = -1;
            }
        }
        if (a[i]){
            for (int j = 0; j <= nowd; j++){
                for (int k = 0; k <= min(cntr, nowp); k++){
                    if (f[j][k] == -1){
                        continue;
                    }
                    if (j){
                        g[j - 1][k] = max(g[j - 1][k], f[j][k]);
                    }
                    else if (k < cntr){
                        g[0][k + 1] = max(g[0][k + 1], f[j][k] + a[i]);
                    }
                    else{
                        g[0][k] = max(g[0][k], f[j][k]);
                    }
                }
            }
            nowp++;
        }
        else{
            for (int j = 0; j <= nowd; j++){
                for (int k = 0; k <= min(cntr, nowp); k++){
                    if (f[j][k] == -1){
                        continue;
                    }
                    if (j < cntd){
                        g[j + 1][k] = max(g[j + 1][k], f[j][k]);
                    }
                    g[j][k] = max(g[j][k], f[j][k]);
                }
            }
            nowd++;
        }
        for (int j = 0; j <= nowd; j++){
            for (int k = 0; k <= min(cntr, nowp); k++){
                f[j][k] = g[j][k];
            }
        }
    }
    cout << f[0][cntr] << endl;
    return 0;
}

:::

P16350 隙间插曲 题解

P16350 隙间插曲题解