[CSP-S 2024] 染色

GitHub 跳转原题关系图返回列表

把两种颜色的历史压成另一色最后值 DP，并用最大/次大状态 O(1) 查询排除当前值后的最优转移。

OJ: luogu

题目 ID: P11233

难度:提高+/省选-

标签:动态规划状态压缩最大次大值

日期: 2026-06-22 18:36

题意

给定数组 A，要把每个位置染成红色或蓝色。

对位置 i，只看它左边最近的同色位置 j：

如果不存在这样的 j，贡献 0；
如果存在且 A_i = A_j，贡献 A_i；
否则贡献 0。

求最大总贡献。

思路

先看一个直接暴力：枚举每个位置染红还是染蓝，然后维护两种颜色的最后值，逐个计算贡献。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int T, n;
int a[MAXN];

long long calc_score(int mask) {
    int last[2];
    last[0] = last[1] = 0;

    long long score = 0;
    for (int i = 1; i <= n; i++) {
        int color = (mask >> (i - 1)) & 1;
        if (last[color] == a[i]) {
            score += a[i];
        }
        last[color] = a[i];
    }

    return score;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }

        long long ans = 0;
        int total = 1 << n;
        for (int mask = 0; mask < total; mask++) {
            ans = max(ans, calc_score(mask));
        }

        cout << ans << '\n';
    }

    return 0;
}

暴力有 2^n 种染色方案，不能处理 n = 2 * 10^5。

关键观察是：处理到某个位置时，一种颜色对后续的影响，只剩下“这种颜色最后一次出现的值”。更早的位置不会再直接影响贡献。

如果直接记录红色最后值和蓝色最后值，会有二维状态。我们可以利用“当前处理完的位置一定属于某一种颜色”来压缩状态。

设处理到上一个位置，last_value = A_{i-1}。令：

符号	含义
`last_value`	上一个位置所在颜色的最后值
`dp[x]`	另一种颜色最后值为 `x` 时的最大得分
`lazy_add`	所有状态共同增加的得分

现在处理 cur = A_i，有两种选择。

第一种：把 cur 染成和上一个位置相同的颜色。若 cur == last_value，那么每个状态都会增加 cur 分；否则不增加。这个转移不会改变另一种颜色的最后值，所以可以用 lazy_add 统一维护。

第二种：把 cur 染成另一种颜色。若这个状态中另一种颜色最后值 x == cur，就增加 cur 分；否则不增加。染完后，刚使用的颜色变成当前颜色，而“另一种颜色”的最后值变成原来的 last_value，所以要更新状态 dp[last_value]。

也就是：

text

1
2
3
4dp[last_value] = max(
  所有 x != cur 的 dp[x],
  dp[cur] + cur
)

注意这里的 dp 说的是实际得分。代码中为了支持统一加分，实际保存的是 dp[x] - lazy_add。

用最大、次大替代 multiset

转移时需要快速求：

text

1所有 x != cur 的最大 dp[x]

其实不需要 multiset。因为每个状态 dp[x] 只会被更新成更大的值，而 lazy_add 是所有状态一起增加，不会改变状态之间的大小关系。

所以只维护两个状态即可：

变量	含义
`best_key, best_value`	当前 `dp[x] - lazy_add` 最大的状态
`second_key, second_value`	key 不同于 `best_key` 的次大状态

查询“排除 cur 后的最大值”时：

如果 best_key != cur，答案就是 best_value + lazy_add；
如果 best_key == cur，答案就是 second_value + lazy_add。

当某个 dp[x] 变大时，只要用它更新最大、次大两个记录即可。

样例 1 的 DP 状态表

下面用样例第一组 1 2 1 展示状态如何转移。表里的 dp[x] 写的是实际得分，x = 0 表示另一种颜色还没有出现过。

处理位置	处理前 `last_value`	当前 `cur`	处理前有效状态	`max_except(cur)`	`dp[cur] + cur`	本轮更新	处理后有效状态
初始	-	`1`	-	-	-	放入空颜色状态 `dp[0]=0`	`dp[0]=0`
`i=2`	`1`	`2`	`dp[0]=0`	`0`	不存在	更新 `dp[1]=0`	`dp[0]=0, dp[1]=0`
`i=3`	`2`	`1`	`dp[0]=0, dp[1]=0`	`0`	`dp[1]+1=1`	更新 `dp[2]=1`	`dp[0]=0, dp[1]=0, dp[2]=1`

第 3 个数为 1 时，状态 dp[1] 表示另一种颜色最后值是 1，如果把当前 1 染到那种颜色上，就能得到贡献 1。于是 dp[2] 被更新成 1，最终答案也是 1。

如果出现 cur == last_value，说明把当前数继续染成和上一个数相同的颜色时，所有状态都会增加 cur。代码不用逐个修改 dp[x]，只需要令 lazy_add += cur。

最后答案就是所有状态的最大值加上 lazy_add。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
const int MAXV = 1000005;
const long long NEG = -(long long)4e18;

int T, n;
int a[MAXN];
bool active_state[MAXV];
long long dp[MAXV]; // dp[x] 表示另一种颜色最后一个数为 x 时的最优得分，统一减去 lazy
long long lazy_add;
vector<int> touched;
int best_key, second_key;              // dp 最大、次大的状态编号
long long best_value, second_value;    // 对应的 dp[x]，不包含 lazy_add

long long get_actual(int x) {
    if (!active_state[x]) {
        return NEG;
    }
    return dp[x] + lazy_add;
}

long long get_max_except(int x) {
    if (best_key == -1) {
        return NEG;
    }
    if (best_key != x) {
        return best_value + lazy_add;
    }
    return second_value + lazy_add;
}

void swap_best() {
    swap(best_key, second_key);
    swap(best_value, second_value);
}

// 某个状态的 dp[x] 只会变大，用最大、次大两个状态就能回答“排除 x 的最大值”。
void update_best(int x) {
    long long value = dp[x];

    if (best_key == x) {
        best_value = value;
        return;
    }

    if (second_key == x) {
        second_value = value;
        if (second_value > best_value) {
            swap_best();
        }
        return;
    }

    if (value > best_value) {
        second_key = best_key;
        second_value = best_value;
        best_key = x;
        best_value = value;
    } else if (value > second_value) {
        second_key = x;
        second_value = value;
    }
}

void set_state(int x, long long actual_value) {
    if (active_state[x] && actual_value <= get_actual(x)) {
        return;
    }

    if (active_state[x]) {
        dp[x] = actual_value - lazy_add;
    } else {
        active_state[x] = true;
        touched.push_back(x);
        dp[x] = actual_value - lazy_add;
    }

    update_best(x);
}

void clear_case() {
    for (int i = 0; i < (int)touched.size(); i++) {
        active_state[touched[i]] = false;
        dp[touched[i]] = 0;
    }
    touched.clear();
    lazy_add = 0;
    best_key = -1;
    second_key = -1;
    best_value = NEG;
    second_value = NEG;
}

void solve_one() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    clear_case();

    int last_value = a[1];
    set_state(0, 0);

    for (int i = 2; i <= n; i++) {
        int x = a[i];

        // 当前数染到“另一种颜色”时，新的另一色最后值会变成 last_value。
        long long candidate = get_max_except(x);
        if (active_state[x]) {
            candidate = max(candidate, get_actual(x) + x);
        }

        // 当前数染到和上一个数相同的颜色，所有状态都会得到这一段相邻相同的贡献。
        if (x == last_value) {
            lazy_add += x;
        }

        long long current = get_actual(last_value);
        if (candidate > current) {
            set_state(last_value, candidate);
        }

        last_value = x;
    }

    long long ans = NEG;
    if (best_key != -1) {
        ans = best_value + lazy_add;
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        solve_one();
    }

    return 0;
}

复杂度

每个位置只进行常数次数组操作和最大、次大状态维护，时间复杂度为 $O(n)$ 。

空间复杂度为 $O(n + V)$ ，其中 V = 10^6 是值域上界。

总结

这题的核心是把“两个颜色的历史”压成“两个颜色的最后值”。进一步利用当前颜色的最后值固定为上一个数，把二维状态压成一维的 dp[x]。

连续染同色带来的统一加分用懒标记维护。改染另一色时需要查询“排除当前值后的最大状态”，由于状态值只会变大，维护最大和次大两个状态就足够了，不需要 multiset。

P11233 [CSP-S 2024] 染色

题目描述

给定一个长度为 $n$ 的正整数数组 $A$ ，其中所有数从左至右排成一排。

你需要将 $A$ 中的每个数染成红色或蓝色之一，然后按如下方式计算最终得分：

设 $C$ 为长度为 $n$ 的整数数组，对于 $A$ 中的每个数 $A_i$ （ $1 \leq i \leq n$ ）：

如果 $A_i$ 左侧没有与其同色的数，则令 $C_i = 0$ 。
否则，记其左侧与其最靠近的同色数为 $A_j$ ，若 $A_i = A_j$ ，则令 $C_i = A_i$ ，否则令 $C_i = 0$ 。

你的最终得分为 $C$ 中所有整数的和，即 $\sum \limits_{i=1}^n C_i$ 。你需要最大化最终得分，请求出最终得分的最大值。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 $T$ ，表示数据组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行包含一个正整数 $n$ ，表示数组长度。

第二行包含 $n$ 个正整数 $A_1, A_2, \dots, A_n$ ，表示数组 $A$ 中的元素。

输出格式

对于每组数据：输出一行包含一个非负整数，表示最终得分的最大可能值。

输入输出样例 #1

输入 #1

text

1
2
3
4
5
6
73
3
1 2 1
4
1 2 3 4
8
3 5 2 5 1 2 1 4

输出 #1

text

说明/提示

【样例 1 解释】

对于第一组数据，以下为三种可能的染色方案：

将 $A_1, A_2$ 染成红色，将 $A_3$ 染成蓝色（ $\red{1}\red{2}\blue{1}$ ），其得分计算方式如下：

对于 $A_1$ ，由于其左侧没有红色的数，所以 $C_1 = 0$ 。
对于 $A_2$ ，其左侧与其最靠近的红色数为 $A_1$ 。由于 $A_1 \neq A_2$ ，所以 $C_2 = 0$ 。
对于 $A_3$ ，由于其左侧没有蓝色的数，所以 $C_3 = 0$ 。
该方案最终得分为 $C_1 + C_2 + C_3 = 0$ 。

将 $A_1, A_2, A_3$ 全部染成红色（ $\red{121}$ ），其得分计算方式如下：

对于 $A_1$ ，由于其左侧没有红色的数，所以 $C_1 = 0$ 。
对于 $A_2$ ，其左侧与其最靠近的红色数为 $A_1$ 。由于 $A_1 \neq A_2$ ，所以 $C_2 = 0$ 。
对于 $A_3$ ，其左侧与其最靠近的红色数为 $A_2$ 。由于 $A_2 \neq A_3$ ，所以 $C_3 = 0$ 。
该方案最终得分为 $C_1 + C_2 + C_3 = 0$ 。

将 $A_1, A_3$ 染成红色，将 $A_2$ 染成蓝色（ $\red{1}\blue{2}\red{1}$ ），其得分计算方式如下：

对于 $A_1$ ，由于其左侧没有红色的数，所以 $C_1 = 0$ 。
对于 $A_2$ ，由于其左侧没有蓝色的数，所以 $C_2 = 0$ 。
对于 $A_3$ ，其左侧与其最靠近的红色数为 $A_1$ 。由于 $A_1 = A_3$ ，所以 $C_3 = A_3 = 1$ 。
该方案最终得分为 $C_1 + C_2 + C_3 = 1$ 。

可以证明，没有染色方案使得最终得分大于 $1$ 。

对于第二组数据，可以证明，任何染色方案的最终得分都是 $0$ 。

对于第三组数据，一种最优的染色方案为将 $A_1, A_2, A_4, A_5, A_7$ 染为红色，将 $A_3, A_6, A_8$ 染为蓝色（ $\red{35}\blue{2}\red{51}\blue{2}\red{1}\blue{4}$ ），其对应 $C = [0, 0, 0, 5, 0, 2, 1, 0]$ ，最终得分为 $8$ 。

【样例 2】

见选手目录下的 color/color2.in 与 color/color2.ans。

【数据范围】

对于所有测试数据，保证： $1\leq T\leq 10$ ， $2\leq n\leq 2\times 10^5$ ， $1\leq A_i\leq 10^6$ 。

::cute-table{tuack}

测试点	$n$	$A_i$
$1\sim 4$	$\leq 15$	$\leq 15$
$5\sim 7$	$\leq 10^2$	$\leq 10^2$
$8\sim 10$	$\leq 2000$	$\leq 2000$
$11,12$	$\leq 2\times 10^4$	$\leq 10^6$
$13\sim 15$	$\leq 2\times 10^5$	$\leq 10$
$16\sim 20$	^	$\leq 10^6$