CF1987F1 Interesting Problem (Easy Version) 题解

题意回顾

给定长度为 $n$ 的数组 $a$。每次操作：

1. 选择一个下标 $i$，满足 $1 \le i < |a|$ 且 $a_i = i$；
2. 删除 $a_i$ 和 $a_{i+1}$，并将剩余部分拼接。

求最多可以执行多少次操作。

核心思路

我们的答案序列是可以通过删除一些区间来得到的。只要知道了每个区间是否可以删除，通过一次简单的 DP 就可以完成删除区间长度最长的计算。

区间 DP 求可删除区间

由于可以拼接，删除形式只有两种，类似于括号序列的删除有 ()() 和 (())。因此可以联想到区间 DP。

考虑从最小的结构来考虑：容易发现只有"左括号"的数字能够通过删除前面的数来使位置与值相同，这一对就可以删掉。因此我们需要记录的是之前删掉的值，而删值是一个动态的过程：删的多的肯定会经过删的少的，即删的少的条件是强于删的多的。

定义 $f_{l,r}$ 表示该区间内能被删除的 前面最少需要删的个数。由于删除每次删两个，奇数的区间不用跑。

转移方程

1. 嵌套形式 (())：外层壳能够消除的前提是内部已经消完了。

   若 $a_l$ 的奇偶性与 $l$ 相同且 $l \ge a_l$，且内部区间 $[l+1, r-1]$ 需要的删除数 $f_{l+1, r-1} \le l - a_l$，则：

   $$f_{l,r} = l - a_l$$

   其中 $l - a_l$ 是外层需要的删除数量。

2. 拼接形式 ()()：枚举中间点 $mid$（$mid$ 为奇数步长）。

   $$f_{l,r} = \min\Big(f_{l,r},\; \max\big(f_{l,mid},\; f_{mid+1,r} - (mid-l+1)\big)\Big) $$

   合并时，右边会因为左边可以减，所以减去 $(mid-l+1)$。

外层 DP 求答案

设 $dp_i$ 表示前缀 $[1, i]$ 中被删除的最大元素个数。

转移：

• 若 $f_{i,j} \le dp_i$（区间能被删除的条件），则：

  $$dp_{j+1} = \max(dp_{j+1},\; dp_i + (j-i+1))$$

• 同时维护 $dp_{i+1} = \max(dp_i, dp_{i+1})$（不删当前位置）。

最终答案为 $dp_{n+1} / 2$（每次操作删除两个数）。

复杂度

• 区间 DP：$O(n^3)$，在 $n \le 100$ 下可行。
• 外层 DP：$O(n^2)$。

AC 代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

namespace fast_IO {
#define IOSIZE 100000
    char ibuf[IOSIZE], obuf[IOSIZE], *p111 = ibuf, *p222 = ibuf, *p333 = obuf;
#define getchar() ((p111==p222)&&(p222=(p111=ibuf)+fread(ibuf,1,IOSIZE,stdin),p111==p222)?(EOF):(*p111++))
#define putchar(x) ((p333==obuf+IOSIZE)&&(fwrite(obuf,p333-obuf,1,stdout),p333=obuf),*p333++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T readdd() {
        T s = 0; int w = 1; char ch;
        while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1;
        if (ch == EOF) return false;
        while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar();
        return s * w;
    }
    template<typename T> inline bool readdd(T &s) {
        s = 0; int w = 1; char ch;
        while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1;
        if (ch == EOF) return false;
        while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar();
        return s *= w, true;
    }
    template<typename T> inline void printtt(T x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) printtt(x / 10);
        putchar(x % 10 + 48);
    }
    inline bool readdd(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool readdd(char *s) {
        char ch; while (ch = getchar(), isspace(ch));
        if (ch == EOF) return false;
        while (!isspace(ch)) *s++ = ch, ch = getchar();
        *s = '\000'; return true;
    }
    inline void printtt(char x) { putchar(x); }
    inline void printtt(char *x) { while (*x) putchar(*x++); }
    inline void printtt(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool readdd(std::string& s) {
        s = ""; char ch;
        while (ch = getchar(), isspace(ch));
        if (ch == EOF) return false;
        while (!isspace(ch)) s += ch, ch = getchar();
        return true;
    }
    inline void printtt(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool readdd(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void printtt(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int readdd(T& a, T1&... other) { return readdd(a) + readdd(other...); }
    template<typename T, typename... T1> inline void printtt(T a, T1... other) { printtt(a), printtt(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p333 - obuf, 1, stdout); } } iooo;
    template<typename T> Fast_IO& operator >> (Fast_IO &iooo, T &b) { return readdd(b), iooo; }
    template<typename T> Fast_IO& operator << (Fast_IO &iooo, T b) { return printtt(b), iooo; }
#define cout iooo
#define cin iooo
#define endl '\n'
} using namespace fast_IO;

const int N = 1000;
int n, a[N], f[N][N], dp[N];

signed main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        memset(f, 63, sizeof(f));
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++) f[i + 1][i] = 0;

        // 区间 DP
        for (int len = 2; len <= n; len += 2) {
            for (int l = 1; l + len - 1 <= n; l++) {
                int r = l + len - 1;

                // 嵌套形式 (())
                if (a[l] % 2 == l % 2 && l >= a[l])
                    if (f[l + 1][r - 1] <= l - a[l])
                        f[l][r] = l - a[l];

                // 拼接形式 ()()
                for (int mid = l + 1; mid <= r - 2; mid += 2) {
                    f[l][r] = min(f[l][r], max(f[l][mid], f[mid + 1][r] - (mid - l + 1)));
                }
            }
        }

        // 外层 DP 求最大删除数
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j += 2) {
                if (f[i][j] <= dp[i])
                    dp[j + 1] = max(dp[j + 1], dp[i] + (j - i + 1));
            }
            dp[i + 1] = max(dp[i], dp[i + 1]);
        }

        cout << dp[n + 1] / 2 << endl;
    }
}