题意

折一根绳子，绳子上的每一段有颜色和厚度（初始都是1），每次要求折叠部分每段颜色对应相同，每次折叠后厚度叠加。修改一段颜色的费用为该段绳子的厚度。

求对于每种颜色，求在以某种方式将绳子折成长度为2的状态后这个颜色仍存在的情况下费用最小。

题解

感觉自己又斯波了。

最显然的一个性质：在开始修改一定不比在折了几段绳子后修改更劣（因为每个线段最多改一次颜色一定优）。

那那些才是最终合法的情况呢？

把绳子最终折成长度为2时的线段画出来，可以观察到，对于所有情况，相邻两段同色的线段距离一定是奇数。

也就是说，例如下面的最终情形是合法的：

1 2 2 1 1 2 2 1 1 1 1 2 2 1 1 2

因此，我们的目标就是把原序列改成只有两种颜色的上述序列。

继续观察性质，发现除了首尾，同色连通块的大小一定是偶数。

但是这个好像对我们没有什么实质性的帮助。

但是观察到这个性质的伴随性质：所有同色连通块的首位的奇偶性相同。

那么对于一种颜色，如果ta最终必须存在，则我们可以枚举这种颜色连通块的首位的奇偶性。

例如对于这个序列：

_ _ 1 1 1 _ _ _ _ 1 1 _ _ _ 1 _

如果要求所有连通块首位为奇数，还要保证每段大小为偶数，则变为：

_ _ 1 1 1 1 _ _ 1 1 1 1 _ _ 1 1

如果要求为偶数，则变为：

_ 1 1 1 1 _ _ _ _ 1 1 _ _ 1 1 _

然后发现，经过修改之后，其他的空填上除颜色\(c\)外数量最多的颜色即可，就可以达到费用最小。

那么对于一个初始序列，修改为包含颜色\(c\)的合法序列的最小费用即为
\[ \min_{修改方案} n - originnum_c - 修改后除颜色c外数量的最大值 \]
复杂度\(O(n)\)。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
int n, m, mx, ans;
int c[N], cnt[N], bul[N];
vector <int> pos[N];

void add (int x) {
    --bul[cnt[x]], ++bul[++cnt[x]];
    mx < cnt[x] ? mx = cnt[x] : 0;
}
void era (int x) {
    --bul[cnt[x]], ++bul[--cnt[x]];
    !bul[mx] ? --mx : 0;
}
int main () {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &c[i]), add(c[i]);
        pos[c[i]].push_back(i);
    }
    for (int i = 1, num; i <= m; ++i) {
        c[0] = c[n + 1] = i, num = pos[i].size();
        for (auto x : pos[i]) {
            era(c[x]);
        }
        for (auto x : pos[i]) {
            if (c[x ^ 1] != i) {
                era(c[x ^ 1]);
            }
        }
        ans = n - num - mx;
        for (auto x : pos[i]) {
            if (c[x ^ 1] != i) {
                add(c[x ^ 1]);
            }
        }
        for (auto x : pos[i]) {
            if (c[((x - 1) ^ 1) + 1] != i) {
                era(c[((x - 1) ^ 1) + 1]);
            }
        }
        printf("%d\n", min(ans, n - num - mx));
        for (auto x : pos[i]) {
            if (c[((x - 1) ^ 1) + 1] != i) {
                add(c[((x - 1) ^ 1) + 1]);
            }
        }
        for (auto x : pos[i]) {
            add(c[x]);
        }
    }
    return 0;
}

loj2336. 「JOI 2017 Final」绳

原文：https://www.cnblogs.com/psimonw/p/11213374.html