CF1987F2 Interesting Problem (Hard Version) 题解

---

一、题意回顾

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

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

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

$n \le 800$，$\sum n \le 800$。

---

二、必要条件分析

考虑如果我们希望 $a_i$ 最终能够被选中（即在其位置满足 $a_i = i$ 并参与操作），那么它应当满足以下条件：

1. $a_i \le i$：因为我们只能删除元素，若 $a_i > i$ 不可能通过操作使 $a_i = i$。
2. $a_i$ 与 $i$ 的奇偶性相同：每次操作只能删去相邻两个元素，下标的前后关系不变，因此操作不会改变下标的奇偶性。
3. 需要在 $[1, i-1]$ 这段前缀中恰好删去 $\dfrac{i - a_i}{2}$ 个数，使得 $a_i$ 移动到位置 $i$ 并满足 $a_i = i$。

---

三、区间 DP：$f_{l, r}$

定义

设 $f_{l, r}$ 表示要将区间 $[l, r]$ 完全删空，最少需要在 $[1, l-1]$ 这段前缀内操作多少次。

转移

首先需要判断 $a_l$ 是否可以被选中（因为不能通过操作前面的数使得 $a_l$ 被删去）。若奇偶性不同或 $l < a_l$，则该区间不可行，跳过。

设 $v = \dfrac{l - a_l}{2}$，即前缀需要删除的次数。

1. 配对删除 $a_l$ 与 $a_r$：

   当 $len = 2$，或内部区间 $[l+1, r-1]$ 需要的删除数满足条件：

   $$f_{l+1,\,r-1} \le v$$

   此时可令 $f_{l, r} = v$。

2. 枚举断点 $k$（$l+1 \le k \le r-1$，且 $k$ 与 $l$ 同奇偶步长，即只取奇数步）：

   $$f_{l, r} = \min\!\Big(f_{l, r},\; \max\!\big(v,\ f_{l, k},\ f_{k+1, r} - \frac{k - l + 1}{2}\big)\Big) $$

   其中 $f_{k+1, r} - \frac{k-l+1}{2}$ 是因为左边区间被删掉后，右边区间所需的删除数会相应地减少。

初始化

所有 $f_{l, r}$ 初始为 $+\infty$。只对长度为偶数的区间进行 DP。

---

四、答案 DP：$g_i$

设 $g_i$ 表示前缀 $[1, i]$ 里最多能操作几次（即最大删除对数）。

转移：枚举前缀 $[1, i]$ 的一段后缀 $[j, i]$（$j$ 与 $i$ 的奇偶性保证区间长度为偶数）。若 $f_{j, i} \le g_{j-1}$，则说明该区间可以被删空，有转移：

$$g_i = \max\!\Big(g_i,\; g_{j-1} + \frac{i - j + 1}{2}\Big) $$

同时还要维护 $g_i = \max(g_i, g_{i-1})$。

最终答案即为 $g_n$。

---

五、复杂度分析

区间 DP 的时间复杂度为 $O(n^3)$，但实际常数很小，且仅对偶数长度区间进行 DP。对于 $n \le 800$，总计算量可控，可以通过。

答案 DP 为 $O(n^2)$。

总体复杂度 $O(n^3)$，空间 $O(n^2)$。

---

六、AC 代码

#include<bits/stdc++.h>
#define For(i, a, b) for(int i = (a); i <= (b); i++)
#define Rof(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 805, INF = 1e9;
int n, a[N], f[N][N], g[N];

void Solve(){
    cin >> n;
    For(i, 1, n) cin >> a[i];
    For(l, 1, n) For(r, 1, n) f[l][r] = INF;

    // 区间 DP
    for(int len = 2; len <= n; len += 2)
        For(l, 1, n - len + 1){
            int r = l + len - 1, v = (l - a[l]) / 2;
            if((l % 2 != a[l] % 2) || l < a[l]) continue;

            // 配对删除 a_l 与 a_r
            if(len == 2 || f[l + 1][r - 1] * 2 <= (l - a[l]))
                f[l][r] = v;

            // 枚举断点
            for(int k = l + 1; k <= r - 1; k += 2){
                int nv = max({v, f[l][k], f[k + 1][r] - (k - l + 1) / 2});
                f[l][r] = min(f[l][r], nv);
            }
        }

    // 答案 DP
    For(i, 1, n){
        g[i] = g[i - 1];
        for(int len = 1; 2 * len <= i; len++)
            if(f[i - 2 * len + 1][i] <= g[i - 2 * len])
                g[i] = max(g[i], g[i - 2 * len] + len);
    }

    cout << g[n] << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T = 1; cin >> T;
    while(T--) Solve();
    return 0;
}