P2145 祖玛 题解

· · 题解

Update 20250121

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

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

10
1 1 2 1 1 3 4 1 1 1

（output: 7 ; ans: 6 )

写在前面

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

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

题意

在本题目下有以下规则：

分析

第一种思路是将连续相同珠子段视为整体，进行区间 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。期待您的新思路！