自动搬运

查看原文

来自洛谷，原作者为

	szh_AK_all S挂分挂到被洛谷7级勾卡线|I can do all things

搬运于2025-08-24 23:07:20，当前版本为作者最后更新于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;
}