P9688 Colo. 的题解

卷王 · 2023-10-03 14:10:42 · 题解

题意转化

原题

别看题目说的那么繁琐，又剪又拼的，其实概括一下就是一句话：

一个有 n 个格子的长纸条，第 i 个格子颜色为 a_i，价值为 b_i，现在要任选 k 种颜色，使得 所有颜色是较大编号 的格子都在 较小编号 的后面，求最大价值。

大体思路

阅读题目可以发现 O(n^3) 是可以过的（洛谷评测机 10^9 开 O2 都能过，10^8 显然是可以的），那么我们可以想到使用 dp。不像某些题解的代码那么长，其实只需要处理一下题目中额外的要求就行了。

设 dp_{i,j} 表示考虑前 i 种颜色并选用第 i 种颜色，一共选择了 j 种颜色的方案数（经典的 问啥设啥）。

转移方程为 dp_{i,j}= \max(dp_{i,j}, dp_{m,j-1}) + b_{a_i}，m 是在前面选中的颜色下标（即 0 \leq m < i）。

我们还要定义两个数组 l,r 分别表示一种颜色第一次出现的位置和最后一次出现的位置，便于在 dp 中判断。这个题目就做完了。

代码如下：

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

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    return x * f;
}

int n, k; ll ans = -1;
int a[507], b[507];
int l[507], r[507]; //这两个数组记录颜色为 i 的区间
ll dp[507][507];
//dp[i][j] 表示考虑前 i 种颜色并选用第 i 种颜色，一共选择了 j 种颜色的方案数

int main() {
    n = read(), k = read();
    for(int i = 1; i <= n; i++) {
        a[i] = read();
        if(l[a[i]] == 0) l[a[i]] = i;
        r[a[i]] = i;
    }
    for(int i = 1; i <= n; i++) b[i] = read();
    memset(dp, -0x3f, sizeof(dp)); dp[0][0] = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= k; j++)
            for(int m = 0; m < i; m++)
                if(a[i] > a[m] && l[a[i]] > r[a[m]]) //如果满足“单调不下降”这一要求
                    if(dp[m][j - 1] >= 0)
                        dp[i][j] = max(dp[i][j], dp[m][j - 1] + b[a[i]]);
    for(int i = 1; i <= n; i++)
        ans = max(ans, dp[i][k]);
    printf("%lld", ans);
    return 0;
}