题解：P11444 [Code+#6] 祖玛

szh_AK_all · 2025-01-21 09:52:34 · 题解

好玩的区间 dp。

竟然是这题题解区的第一篇题解诶。

分析

根据套路，先设 f_{l,r} 表示删完区间 [l,r] 内的数可获得的最大权值。但是容易发现区间 [l,r] 还可能与 [1,l-1] 中的数有联系，因为可能在删完 [l,r] 的一个前缀 [l,k] 时，[k+1,r] 与 [1,l-1] 可以拼接在一起，即 a_{l-1}=a_{k+1}。

于是设 f_{l,r,x,p} 表示删完区间 [l,r] 内的数，且需要或不需要删掉 a_{l-1}（p 为 0 或 1），如果要删的话则删 x 个的最大权值，接下来转移方程便很好推了。

枚举断点 k，则有两种转移：

• 当 a_k=a_{l-1} 且 p=1 时，可以选择先将区间 [l,k-1] 删完，再将区间 [1,l-1] 与区间 [k,r] 拼起来，答案即 f_{l,k-1,0,0}+f_{k+1,r,x+1,1}。注意此时区间 [l,k-1] 是与外界隔绝的。

• 当 X_{min}\le x \le X_{max} 或者 x=0 时，考虑将区间 [l,r] 直接从 k 处断开。那么与 k 有联系的区间是 [k+1,r]，并且此时会产生 x^2 的权值，答案即为 f_{l,k-1,0,0}+f_{k+1,r,1,1}+x^2。

细节：

• 答案应是所有可以转移到的 f 的最大值；

• 个人认为写记忆化搜索更方便点；

• 边界情况需要特判，即 l>r 时，权值为 x^2（前提是 x 没有越界）；

• 转移的开始可以有很多种，这里是用 f_{i,n,1,1}(2\le i\le n) 及 f_{1,n,0,0} 作为转移的开始。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[105], f[105][105][105][2], mi, ma, tmp, k;

int dfs(int l, int r, int xuan, int p) {
    if (l > r) {
        if (xuan && (mi > xuan || xuan > ma))
            return -1000000000;
        tmp = max(tmp, xuan * xuan);
        return xuan * xuan;
    }
    if (f[l][r][xuan][p] > k)
        return f[l][r][xuan][p];
    if (xuan > ma)
        return 0;
    int ans = 0;
    for (int k = l; k <= r; k++)
        if (p && a[k] == a[l - 1])
            ans = max(ans, dfs(l, k - 1, 0, 0) + dfs(k + 1, r, xuan + 1, 1));
    for (int k = l; k <= r; k++)
        if ((!xuan || (mi <= xuan && xuan <= ma)))
            ans = max(ans, dfs(l, k - 1, 0, 0) + dfs(k + 1, r, 1, 1) + xuan * xuan);
    tmp = max(tmp, ans);
    return f[l][r][xuan][p] = ans;
}

signed main() {
    memset(f, -0x3f, sizeof(f));
    k = f[0][0][0][0];
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> mi >> ma;
    for (int i = 1; i <= n; i++)
        dfs(i + 1, n, 1, 1);
    tmp = max(tmp, dfs(1, n, 0, 0));
    cout << tmp;
}