AT_abc345_e [ABC345E] Colorful Subsequence

题目描述

有 $N$ 个球排成一列。
从左到右第 $i$ 个球的颜色为 $C_i$，价值为 $V_i$。

高桥君想要从这列球中恰好移除 $K$ 个球，使得剩下的球按照原本的顺序排列时，相同颜色的球不会相邻。同时，在满足上述条件的前提下，他希望剩下球的价值总和尽可能大。

请判断高桥君是否能够通过移除 $K$ 个球，使得剩下的球中没有相邻的球颜色相同。如果可以，请求出剩下球的价值总和的最大可能值；如果不可以，请输出 $-1$。

输入格式

输入按以下格式从标准输入读入。

$N$ $K$
$C_1$ $V_1$
$C_2$ $V_2$
$\vdots$
$C_N$ $V_N$

输出格式

如果高桥君能够移除 $K$ 个球，使得剩下的球中没有相邻的球颜色相同，则输出剩下球的最大价值总和（一个整数）。如果无法做到，则输出 $-1$。

输入输出样例 #1

输入 #1

5 2
1 1
3 5
3 3
1 4
1 2

输出 #1

10

输入输出样例 #2

输入 #2

3 1
1 10
1 10
1 10

输出 #2

-1

输入输出样例 #3

输入 #3

3 1
1 1
2 2
3 3

输出 #3

5

说明/提示

限制条件

• $1 \leq K < N \leq 2 \times 10^5$
• $K \leq 500$
• $1 \leq C_i \leq N$
• $1 \leq V_i \leq 10^9$
• 输入均为整数

样例解释 1

如果移除第 $3$、$5$ 个球，剩下的球从左到右颜色为 $1,3,1$，因此任意相邻的两个球颜色都不同，满足条件。此时，剩下球的价值和为 $V_1+V_2+V_4=1+5+4=10$。
除此之外，从 $5$ 个球中移除 $2$ 个球且满足相邻颜色不同的方法还有其他，但移除第 $3$、$5$ 个球时剩下球的价值和最大。因此输出 $10$。

样例解释 2

无论移除哪一个球，颜色为 $1$ 的球都会相邻。因此输出 $-1$。

样例解释 3

请注意，必须恰好移除 $K$ 个球。

由 ChatGPT 4.1 翻译