题解：CF1987F2 Interesting Problem (Hard Version)

· · 题解

场上瞪了一个小时一点不会，狠狠意识到我对区间 dp 一无所知。

考虑如果我们希望 a_i 最终被选中过，那么它应当满足下面的条件：

结合第三条与数据范围，可以想到一个区间 dp：设 f_{l,r} 表示要将区间 [l,r] 删空，最少要在 [1,l-1] 这段前缀内操作几次，转移前首先要判断 a_l 是否可以被选中，因为不能通过操作前面的数使得 a_l 被删去，然后设 v=\frac{l-a_l}{2}，转移考虑枚举断点 k，则 \max\{v,f_{l,k},f_{k+1,r}-\frac{k-l+1}{2}\}\to f_{l,r} 即可。

还有一种特殊的转移，我们可以将 a_l 与 a_r 配对删除，条件为 f_{l+1,r-1}\le \frac{l-a_l}{2}。

随后考虑如何求答案，令 g_i 表示 [1,i] 里最多能操作几次，转移时枚举前缀 [1,i] 的一段后缀 [j,i]，如果 f_{j,i}\le g_{j-1} 即可有转移 g_{j-1}+\frac{i-j+1}{2}\to g_i，也就是代表 [j,i] 这段能被删空。

时间复杂度 O(n^3)，但区间 dp 本身拥有很小常数且本题我们还只需要对长度为偶数的区间进行 dp，所以可以通过。

#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;
    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;
            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);
            }
        }
    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;
}