自动搬运

查看原文

来自洛谷，原作者为

	AchorX 我？这很难评

搬运于2025-08-24 21:34:28，当前版本为作者最后更新于2024-05-27 17:45:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Update 20250121

如果你是大牛，建议直接抬走我的，跳过交流这一步，因为我大概率会听不懂你的想法 TT

修了一下图片。无法通过数据：

10
1 1 2 1 1 3 4 1 1 1

（output: $7$ ; ans: $6$ )

写在前面

Q：为什么要写这篇题解？

A：我综合了一下原有题解的两种思路，杂交了一个目前过掉数据最多的，复杂度不正确的代码。也就是说，仍然不是正解。

题意

在本题目下有以下规则：

• 起始时无论有几个连续相同的珠子都无法消除。
• 可在任意两颗珠子中插入任意颜色珠子。
• 当插入珠子后，包含该珠子的 连续相同珠子段 若长度大于 $2$ ，则消除。
• 消除后，若消除段前的珠子与消除段后的珠子颜色相同且长度和大于 $2$ ，再次消除。

分析

第一种思路是将连续相同珠子段视为整体，进行区间 DP 。

可以分以下情况：（用o代表一个珠子，用【】代表一段）

1. o【】、【】【】 即分段。
2. o【】o 前后珠子一样可以凑一起。
3. o【】o【】o 同理。
4. o【】o【】o【】o 可以先消除左右两个【】，再消除中间的。
5. o【】o【】o【】o【】o 本质上和3是一样的，多加同理。

但是我们发现了问题

我们不得不把视为整体的部分分解，于是有了第二种思路。

不把起始珠子合并，同样的，有

1. o【】、【】【】
2. o【】o
3. o【】o【】o
4. o【】o【】o【】o

以上均同理。

前三个的计算很简单，$4$ 要寻找四个颜色相同且孤立的珠子，那就要在区间中枚举每一坨珠子（注意不是一个），并且要有两重循环来寻找，复杂度算上外层区间 DP ，接近（因为跑不满）于 $O(n^4)$ ，显然错误。 但我目前没有找到合适的解决方法。

综上所述，我们可以采用将两种 DP 结合起来的方法来解决此题（部分）。

代码如下（部分参考其他题解）：

#include<bits/stdc++.h>
using namespace std;
const int N = 5e2 + 5;
int n, a[N], b[N], num[N], w, cnt, dp[N][N], to[N], ttoo[N], f[N][N];
void read() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	for (int i = 1; i <= n; ++i) {
		w = a[i], b[++cnt] = a[i], num[cnt] = 1, to[cnt] = i, ttoo[i] = cnt;
		while (a[i + 1] == w) num[cnt] ++, i++, ttoo[i] = cnt;
	}
	memset(f, 0x3f, sizeof f);
	for (int len = 1; len <= n; ++len)
		for (int i = 1, j = len; j <= n; ++i, ++j) {
			if (ttoo[i] == ttoo[j]) {
				f[i][j] = max(1, 2 - j + i);
				continue;
			}
			for (int k = i; k < j; ++k)
				f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
			if (a[i] == a[j]) {
				int x = to[ttoo[i] + 1], y = to[ttoo[j]] - 1;//第一个与i, j颜色不同的
				int len1 = x - i, len2 = j - y;//此区间内与i,j 紧挨着 且颜色相同的个数
				f[i][j] = min(f[i][j], f[x][y] + (len1 + len2 < 3));
				if (min(len1, len2) < 3) continue;
				for (int k = x + 1; k <= y - 1; ++k)
					if (a[k] == a[i] && num[ttoo[k]] + min(len1, len2) < 3)
						f[i][j] = min(f[i][j], f[x][k - 1] + f[k + num[ttoo[k]]][y]);
			}
		}
	memset(dp, 0x3f, sizeof dp);
	for (int i = 1; i <= cnt; ++i) dp[i][i] = (num[i] >= 2 ? 1 : 2);
	for (int len = 1; len < cnt; ++len)
		for (int i = 1, j = i + len; j <= cnt; ++i, ++j) {
			if (ttoo[to[i] + num[i] - 1] == i && ttoo[to[j] - num[i] + 1] == j) dp[i][j] = min(dp[i][j], f[to[i]][to[j]]);
			if (b[i] == b[j] && len > 1) dp[i][j] = min(dp[i][j], dp[i + 1][j - 1] + (num[i] + num[j] <= 2));
			if (b[i] == b[j]) {
				for (int k = i + 1; k < j; ++k)
					if (b[i] == b[k] && (num[i] + num[k] < 3 || num[k] + num[j] < 3)) dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k + 1][j - 1]);
				if (num[i] == num[j] && num[i] == 1)
					for (int x = i + 1; x < j; ++x)
						for (int y = x + 1; y < j; ++y)
							if (b[x] == b[y] && b[x] == b[i] && num[x] == num[y] && num[x] == 1)
								dp[i][j] = min(dp[i][j], dp[i + 1][x - 1] + dp[x + 1][y - 1] + dp[y + 1][j - 1]);
			}
			for (int k = i; k < j; ++k) {
				dp[i][j] = min(dp[i][k] + dp[k + 1][j], dp[i][j]);
				dp[i][j] = min(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + (num[k] >= 2 ? 1 : 2));
			}
		}
	printf("%d", dp[1][cnt]);
}
int main() {
	read();
	return 0;
}

再次声明，此代码复杂度错误，思路不太正确，本篇题解仅为思路参考。当然，这么写可以 AC。期待您的新思路！