[CSP-S 2024] 染色

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

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

OJ: luogu

题目 ID: P11233

难度:提高+/省选-

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

创建: 2026-06-22 18:36

更新: 2026-10-07 10:45

形式化题目

给定正整数数组 $A_1,\dots,A_n$ ，把每个位置染成红色或蓝色。

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

不存在这样的 $j$ ： $C_i=0$ ；
存在且 $A_i=A_j$ ： $C_i=A_i$ ；
否则： $C_i=0$ 。

求 $\sum_i C_i$ 的最大值。

暴力解法

思路

枚举所有 $2^n$ 种染色方案。每种方案从左到右扫一遍，维护每种颜色最后一个值，相等就累加 $A_i$ 。

代码

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-01 22:57
 * update_at: 2026-10-01 22:57
 */
// brute.cpp：小数据暴力解，枚举所有染色方案并逐个计算得分。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 25;   // 暴力只服务小数据，n 取到 20 左右（要枚举 2^n 种方案）

int T, n;
int a[MAXN];

// 按 mask 的每一位决定第 i 个数染哪种颜色，逐个算出贡献。
ll calc_score(int mask) {
    int last[2];
    last[0] = last[1] = 0;   // 每种颜色还没出现过时，最后值记作 0

    ll score = 0;
    for (int i = 1; i <= n; i++) {
        int color = (mask >> (i - 1)) & 1;

        // 左边最近的同色数就是该颜色的最后值；相等才得 A_i 分。
        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];
        }

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

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

    return 0;
}

复杂度

时间复杂度 $O(2^n\cdot n)$ ，空间 $O(n)$ 。

瓶颈

$n$ 最大 $2\times10^5$ ， $2^n$ 完全不可行。但暴力里有一个很有用的提示：判断 $C_i$ 时，一种颜色左边更早的数都不重要，只有该颜色最后出现的值有用。

正解

思路

状态只留两个“最后值”

处理完前 $i-1$ 个位置后，决定后续收益的只有两个数：红色最后值和蓝色最后值。于是把状态压成这两个值。

再进一步压缩：第 $i-1$ 个位置一定属于某一种颜色，设它的值为 $last$ 。于是

符号	含义
$last$	上一个位置所在颜色的最后值
$dp[x]$	另一种颜色最后值为 $x$ 时的最大得分
$lazy\_add$	所有状态共享的加分

用 $x=0$ 表示“另一种颜色还没出现过”（ $A_i\geqslant1$ ，不会冲突）。

两种染法

设 $cur=A_i$ ，逐个状态考虑：

选择一：把 $cur$ 染成和上一个位置相同的颜色。

此时同色的最近位置就是 $i-1$ ，只有 $cur=last$ 才得 $cur$ 分。这个加分对所有状态都一样，而且不改变“另一色最后值”，所以用 $lazy\_add$ 统一加即可。

选择二：把 $cur$ 染成另一种颜色。

此时同色的最近位置是“另一色最后值” $x$ ，只有 $x=cur$ 才得 $cur$ 分。染完之后角色互换——原另一色变成当前色，原当前色（最后值 $last$ ）变成另一色。所以要把结果写进状态 $last$ ：

dp[last]\leftarrow\max\Bigl(\max_{y\neq cur}dp[y],\ dp[cur]+cur\Bigr).

用最大、次大代替 multiset

转移里要快速求 $\max_{y\neq cur}dp[y]$ 。不需要 multiset：

$dp[x]$ 只会被更新成更大的值；
$lazy\_add$ 对所有状态一视同仁，不改变它们之间的大小关系。

所以只要维护两个状态——最大和次大：

变量	含义
`best_key`, `best_value`	$dp$ 值最大的状态
`second_key`, `second_value`	与 `best_key` 不同的次大状态

查询“排除 $cur$ 的最大值”时：best_key != cur 就取最大，否则取次大。某个 $dp[x]$ 变大时，用它刷新这两个记录即可，全程 $O(1)$ 。

样例推演

下面用样例第一组 $A=[1,2,1]$ 展示状态转移。表里的得分写实际值， $x=0$ 表示另一色还没出现。

位置	处理前 $last$	$cur$	$\max_{y\neq cur}dp[y]$	$dp[cur]+cur$	本轮更新	处理后状态
初始	无	$1$	无	无	放入空色状态	$dp[0]=0$
$i=2$	$1$	$2$	$0$	状态不存在	更新 $dp[1]=0$	$dp[0]=0,\ dp[1]=0$
$i=3$	$2$	$1$	$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$ （连续两个同值），选染同色会给所有状态加 $cur$ ，代码只需 lazy_add += cur，不动任何 $dp[x]$ 。最后答案是 $\max_x dp[x]+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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-01 22:57
 * update_at: 2026-10-01 22:57
 */
// main.cpp：把两种颜色的历史压成“另一色最后值”的 DP，用最大/次大状态 O(1) 查排除当前值后的最优转移。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 200005;   // n <= 2e5
const int MAXV = 1000005;  // A_i <= 1e6，值直接当 DP 下标

// 哨兵值，表示“这个状态还不存在”。取 LL 最小值的一半而不是本身，给加法留出余量。
const ll NEG_INF = LLONG_MIN / 2;

int T, n;
int a[MAXN];           // a[i]：第 i 个数，值域不超过 1e6，正好当 DP 下标用，所以用 int
bool active_state[MAXV]; // active_state[x]：状态 x 是否已经出现过
ll dp[MAXV];           // dp[x]：另一颜色最后值为 x 时的最大得分（已减去 lazy_add）
ll lazy_add;           // 所有状态共享的加分，避免逐个改 dp
vector<int> touched;   // 本组数据用到过的状态编号，方便整组清理

// 最大、次大的状态编号与 dp 值（不含 lazy_add）。
// dp[x] 只会变大，lazy_add 对所有状态一视同仁，所以两个状态就够回答“排除某值后的最大值”。
int best_key, second_key;
ll best_value, second_value;

// 取状态 x 的真实得分；状态不存在时返回哨兵。
ll get_actual(int x) {
    if (!active_state[x]) {
        return NEG_INF;
    }
    return dp[x] + lazy_add;
}

// 取“除了状态 x 之外”的最大真实得分。
ll get_max_except(int x) {
    if (best_key == -1) {
        return NEG_INF;
    }
    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 值变大后，用它刷新最大、次大两个记录。
void update_best(int x) {
    ll 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;
    }
}

// 把状态 x 的真实得分抬高到 actual_value（只有更优才写入）。
void set_state(int x, ll actual_value) {
    if (active_state[x] && actual_value <= get_actual(x)) {
        return;
    }

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

    update_best(x);
}

// 每组数据结束时，只清本组真正用过的状态，避免 O(值域) 重置。
void clear_case() {
    int cnt = touched.size();
    for (int i = 0; i < cnt; i++) {
        active_state[touched[i]] = false;
        dp[touched[i]] = 0;
    }
    touched.clear();

    lazy_add = 0;
    best_key = -1;
    second_key = -1;
    best_value = NEG_INF;
    second_value = NEG_INF;
}

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

    clear_case();

    // 开局把第一个数染成任意一种颜色，此时“另一种颜色还没出现”，用状态 0 表示。
    int last_value = a[1];
    set_state(0, 0);

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

        // 选择二：把当前数染到另一种颜色上。
        // 之后角色互换，“另一色最后值”变成原来的 last_value。
        ll candidate = get_max_except(x);
        if (active_state[x]) {
            candidate = max(candidate, get_actual(x) + x);
        }

        // 选择一：把当前数染成和上一个数相同的颜色。
        // 只有 x == last_value 时才贡献 x，且所有状态一起加，用 lazy_add 表示。
        if (x == last_value) {
            lazy_add += x;
        }

        // 两种选择里取更优的，写到状态 last_value 上。
        ll current = get_actual(last_value);
        if (candidate > current) {
            set_state(last_value, candidate);
        }

        last_value = x;
    }

    ll ans = NEG_INF;
    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$ 是值域上界。多组数据间只清空真正用过的状态，均摊仍是线性。

总结

这题做了三层压缩：

把“两种颜色的整段历史”压成“两个颜色的最后值”——只有最近的同色数影响 $C_i$ ；
再利用“上一个位置一定属于当前颜色”，把二维状态压成一维的 $dp[x]$ ；
连续染同色带来的统一加分用懒标记维护，改染另一色时需要的“排除当前值的最大值”用最大、次大两个状态 $O(1)$ 回答。

第三层是本题的实现关键：正因为 $dp[x]$ 单调变大、懒标记又不改变状态间的大小关系，才不需要 multiset 这类可删堆结构。

本文的 main.cpp 已用枚举全部染色方案的 brute.cpp 对拍 $600$ 组随机数据，并对 $n\leqslant 8$ 、取值 $\{1,2,3\}$ 的全部 $9840$ 个数组做了穷举核对，题面样例通过。

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$