2688. 「POI2015 R3」洗车 Car washes 题解

问题分析

有 $n$ 家洗车店排成一排，编号 $1$ 到 $n$，需要给每家店设定价格 $p_i$。

有 $m$ 个顾客：

• 顾客 $i$ 会查看区间 $[a_i, b_i]$ 内的所有店
• 选择这些店中价格最低的一家消费（价格为该店的价格）
• 但如果这个最低价格 $> c_i$，那么顾客不消费

目标：设定 $p_i$ 的值，使得消费总额最大。

关键点：

• $n$ 很小（$n \le 50$），$m$ 较大（$m \le 4000$）
• 价格 $p_i$ 可以很大（$\le 5\times 10^5$）

关键观察

1. 顾客行为分析

对于顾客 $i$：

• 如果区间 $[a_i, b_i]$ 的最小价格 $\min(p_{a_i..b_i}) \le c_i$，则顾客消费，支付金额为这个最小值
• 否则顾客不消费

2. 区间最小值问题

一个区间 $[l, r]$ 的最小值由这个区间内价格最低的店决定。

如果顾客 $i$ 在区间 $[a_i, b_i]$ 消费，那么他支付的价格一定是这个区间内某家店的价格，且这个价格是区间内最小的。

3. 思路：枚举最小值位置

考虑区间 $[l, r]$，假设它的最小值出现在位置 $k$（$l \le k \le r$），值为 $v$。

那么：

• 所有完全包含在 $[l, r]$ 内且包含位置 $k$ 的区间，如果 $v \le c_i$，则这些顾客会消费并支付 $v$
• 但还要考虑 $v$ 是不是整个区间的最小值

我们可以用区间DP的思想。

算法设计

1. 离散化价格

由于价格值域很大，但顾客的 $c_i$ 最多 $4000$ 个不同的值，我们可以考虑：

• 将所有顾客的 $c_i$ 收集起来，排序去重
• 价格 $p_i$ 只可能取这些 $c_i$ 值，或者某个 $c_i+1$（为了让顾客刚好不消费？）

但实际上，最优解中 $p_i$ 一定是某个顾客的 $c_i$ 值。证明：如果 $p_i$ 不是任何顾客的 $c_i$，我们可以适当调整到最近的 $c_i$ 值，不会减少收入。

设所有 $c_i$ 排序去重后为 $v_1 < v_2 < \cdots < v_K$，$K \le m \le 4000$。

2. 区间DP状态

定义 $dp[l][r][h]$：考虑区间 $[l, r]$，区间内的最小价格至少为 $v_h$（即所有店的价格都 $\ge v_h$），且恰好有一家店的价格为 $v_h$（是最小值），能获得的最大收入。

但这个状态不够，因为最小值可能大于 $v_h$。

更好的定义： $dp[l][r]$：区间 $[l, r]$ 能获得的最大总收入（仅考虑完全包含在 $[l, r]$ 内的顾客）。

转移时，我们枚举区间 $[l, r]$ 中最小值的位置 $k$ 和最小值 $v$：

• 设位置 $k$ 的价格为 $v$
• 区间 $[l, r]$ 内其他店的价格都 $\ge v$
• 那么 $[l, r]$ 被分成三个部分：$[l, k-1]$，位置 $k$，$[k+1, r]$
• $[l, k-1]$ 和 $[k+1, r]$ 是独立子问题，但它们的最小值必须 $\ge v$

3. 状态设计

设 $f[l][r][h]$ 表示区间 $[l, r]$ 内的所有店价格都 $\ge v_h$ 时的最大收入。

转移时，枚举最小值的位置 $k$ 和最小值 $v_h$：

• 位置 $k$ 的价格设为 $v_h$
• $[l, k-1]$ 的价格都 $\ge v_h$，所以从 $f[l][k-1][h]$ 转移
• $[k+1, r]$ 的价格都 $\ge v_h$，所以从 $f[k+1][r][h]$ 转移
• 加上位置 $k$ 的价格 $v_h$ 带来的收入：所有完全包含在 $[l, r]$ 内且包含 $k$ 的顾客 $i$，如果 $c_i \ge v_h$，则这些顾客会消费并支付 $v_h$

4. 计算顾客贡献

对于固定的 $l, r, k, h$，我们需要计算： 有多少顾客 $i$ 满足：

1. $l \le a_i \le k \le b_i \le r$（完全包含在 $[l, r]$ 内且包含 $k$）
2. $c_i \ge v_h$（因为区间最小值为 $v_h$，如果 $c_i \ge v_h$，顾客会消费）

设这个数量为 $cnt[l][r][k][h]$，那么贡献为 $cnt[l][r][k][h] \times v_h$。

5. 转移方程

$$f[l][r][h] = \max \begin{cases} f[l][r][h+1] & \text{(价格都} \ge v_{h+1} \text{，即最小值更大)} \\ \max_{k=l}^r \left( f[l][k-1][h] + f[k+1][r][h] + cnt[l][r][k][h] \times v_h \right) & \text{(位置k为最小值)} \end{cases} $$

边界：

• 当 $l > r$ 时，$f[l][r][h] = 0$
• 当 $h > K$ 时，$f[l][r][h] = 0$（价格无穷大，没有顾客消费）

6. 复杂度分析

• 状态数：$O(n^2 \times K)$，其中 $n \le 50, K \le 4000$，最多 $50^2 \times 4000 = 10^7$，较大但可能可行
• 转移：枚举 $k$，$O(n)$
• 总复杂度：$O(n^3 \times K) \approx 50^3 \times 4000 = 5 \times 10^8$，太大

7. 优化

我们可以预处理 $cnt[l][r][k][h]$，但需要 $O(n^4 \times K)$ 空间和时间，不可行。

优化思路：

• 对于每个顾客 $i$，它对 $cnt[l][r][k][h]$ 有贡献当且仅当 $l \le a_i \le k \le b_i \le r$ 且 $c_i \ge v_h$
• 我们可以预处理二维前缀和

更简单：在 DP 过程中动态计算贡献。

详细算法

1. 预处理

// 读入数据
int n, m;
cin >> n >> m;

vector<int> a(m), b(m), c(m);
vector<int> values;  // 所有c_i值

for (int i = 0; i < m; i++) {
    cin >> a[i] >> b[i] >> c[i];
    a[i]--; b[i]--;  // 转为0-based
    values.push_back(c[i]);
}

// 离散化
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());
int K = values.size();

2. 辅助函数

计算在区间 $[l, r]$ 内，位置 $k$ 设为最小值 $v_h$ 时，完全包含在 $[l, r]$ 内且包含 $k$ 的顾客数量。

// 预处理每个顾客的贡献
// 对于每个顾客i，它会对所有满足条件的(l,r,k,h)有贡献

// 更高效：在DP时实时计算
int count_customers(int l, int r, int k, int h) {
    int cnt = 0;
    int v = values[h];
    for (int i = 0; i < m; i++) {
        if (a[i] >= l && a[i] <= k && k <= b[i] && b[i] <= r && c[i] >= v) {
            cnt++;
        }
    }
    return cnt;
}

3. 记忆化搜索DP

vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(K, -1)));

// 记忆化搜索
int solve(int l, int r, int h) {
    if (l > r) return 0;
    if (h == K) return 0;  // 价格大于所有c_i，没有顾客消费
    
    if (dp[l][r][h] != -1) return dp[l][r][h];
    
    // 情况1：区间内所有价格都 >= v_{h+1}
    int res = solve(l, r, h + 1);
    
    // 情况2：枚举最小值位置k
    for (int k = l; k <= r; k++) {
        // 位置k的价格为v_h
        // [l, k-1]和[k+1, r]的价格都 >= v_h
        int left = solve(l, k - 1, h);
        int right = solve(k + 1, r, h);
        
        // 计算顾客贡献
        int cnt = count_customers(l, r, k, h);
        int profit = cnt * values[h];
        
        res = max(res, left + right + profit);
    }
    
    return dp[l][r][h] = res;
}

4. 复杂度问题

上面的算法复杂度：

• 状态数：$O(n^2 K)$
• 每个状态需要 $O(n \times m)$ 计算顾客数（因为要遍历所有顾客）
• 总复杂度：$O(n^3 K m)$，太大

5. 优化顾客计数

我们可以预处理二维前缀和： 设 $pref[l][r][k][h]$ 表示满足 $a_i \ge l, b_i \le r, a_i \le k \le b_i, c_i \ge v_h$ 的顾客数。

但这是四维数组，太大。

更好的方法：对于固定的 $k$ 和 $h$，预处理 $cnt[l][r]$ 表示满足 $l \le a_i \le k \le b_i \le r$ 且 $c_i \ge v_h$ 的顾客数。

我们可以用二维前缀和：

// 对于每个k和h，预处理sum[l][r]
vector<vector<int>> pre_sum(n, vector<int>(n, 0));
for (int i = 0; i < m; i++) {
    if (c[i] >= values[h]) {
        // 顾客i对哪些(l,r,k)有贡献？
        // 需要 l <= a[i] <= k <= b[i] <= r
        // 对于固定的k，需要 l <= a[i], r >= b[i]
        // 所以对于所有 l <= a[i], r >= b[i]，都有贡献
    }
}

6. 更聪明的DP

实际上，官方题解使用了不同的状态定义。

定义 $dp[l][r]$ 表示区间 $[l, r]$ 的最大收入。

转移：枚举区间 $[l, r]$ 中最小值的位置 $k$：

• 设 $p_k = x$
• 那么 $[l, r]$ 内所有店价格 $\ge x$
• 所有完全包含 $[l, r]$ 且包含 $k$ 的顾客，如果 $c_i \ge x$，则贡献 $x$

我们需要选择 $x$ 使得收入最大。

对于固定的 $k$，收入为：

$$profit(k, x) = \left( \sum_{i: l \le a_i \le k \le b_i \le r \text{且} c_i \ge x} 1 \right) \times x + dp[l][k-1] + dp[k+1][r] $$

注意：$dp[l][k-1]$ 和 $dp[k+1][r]$ 与 $x$ 无关，因为 $[l, k-1]$ 和 $[k+1, r]$ 的最小值 $\ge x$，但它们的实际最小值可能更大。

所以我们需要修改状态：$dp[l][r][min]$ 表示区间 $[l, r]$ 内所有价格 $\ge min$ 的最大收入。

最终算法

由于 $n$ 很小，我们可以用 $O(n^3 \times K)$ 的DP，但需要优化常数。

下面是简化版实现：

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

const int MAXN = 55;
const int MAXM = 4005;

int n, m;
int a[MAXM], b[MAXM], c[MAXM];
vector<int> values;

// dp[l][r][h]: 区间[l,r]内所有价格 >= values[h]的最大收入
int dp[MAXN][MAXN][MAXM];
// 记录决策
int choice_k[MAXN][MAXN][MAXM];
int choice_h[MAXN][MAXN][MAXM];

// 预处理：对于每个区间[l,r]和位置k，计算每个价格h的顾客数
vector<int> cnt[MAXN][MAXN][MAXN];  // cnt[l][r][k][h]

void precompute() {
    for (int l = 0; l < n; l++) {
        for (int r = l; r < n; r++) {
            for (int k = l; k <= r; k++) {
                cnt[l][r][k].resize(values.size(), 0);
                for (int i = 0; i < m; i++) {
                    if (a[i] >= l && a[i] <= k && k <= b[i] && b[i] <= r) {
                        // 找到c[i]在values中的位置
                        auto it = lower_bound(values.begin(), values.end(), c[i]);
                        if (it != values.end()) {
                            int idx = it - values.begin();
                            // 对于所有h <= idx，这个顾客都会贡献
                            for (int h = 0; h <= idx; h++) {
                                cnt[l][r][k][h]++;
                            }
                        }
                    }
                }
            }
        }
    }
}

int solve(int l, int r, int h) {
    if (l > r) return 0;
    if (h == (int)values.size()) return 0;
    
    if (dp[l][r][h] != -1) return dp[l][r][h];
    
    // 情况1：价格都 >= values[h+1]
    int res1 = solve(l, r, h + 1);
    int best = res1;
    int best_k = -1;
    int best_h = h + 1;
    
    // 情况2：枚举最小值位置k，价格为values[h]
    for (int k = l; k <= r; k++) {
        int left = solve(l, k - 1, h);
        int right = solve(k + 1, r, h);
        int profit = cnt[l][r][k][h] * values[h];
        int total = left + right + profit;
        
        if (total > best) {
            best = total;
            best_k = k;
            best_h = h;
        }
    }
    
    dp[l][r][h] = best;
    choice_k[l][r][h] = best_k;
    choice_h[l][r][h] = best_h;
    
    return best;
}

// 根据决策重建方案
vector<int> prices(n);
void build(int l, int r, int h, int min_val) {
    if (l > r) return;
    
    if (choice_k[l][r][h] == -1) {
        // 情况1：所有价格 >= values[h+1]
        build(l, r, h + 1, values[h + 1]);
    } else {
        int k = choice_k[l][r][h];
        int val = values[h];
        prices[k] = val;
        
        // 递归处理左右区间，最小值至少为val
        build(l, k - 1, h, val);
        build(k + 1, r, h, val);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i] >> c[i];
        a[i]--; b[i]--;
        values.push_back(c[i]);
    }
    
    // 离散化
    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());
    
    // 预处理cnt
    precompute();
    
    // 初始化DP
    memset(dp, -1, sizeof(dp));
    memset(choice_k, -1, sizeof(choice_k));
    memset(choice_h, -1, sizeof(choice_h));
    
    // 计算答案
    int ans = solve(0, n - 1, 0);
    cout << ans << endl;
    
    // 重建方案
    build(0, n - 1, 0, values[0]);
    
    // 输出价格
    for (int i = 0; i < n; i++) {
        cout << prices[i] << (i == n - 1 ? '\n' : ' ');
    }
    
    return 0;
}

复杂度分析

预处理 cnt：

• 需要计算所有 $l, r, k, h$ 的组合
• $n \le 50$，$K \le 4000$
• 复杂度：$O(n^3 \times K \times m)$，太大（$50^3 \times 4000 \times 4000 ≈ 2 \times 10^{11}$）

优化

实际上，对于固定的 $k$，我们可以预处理每个顾客对哪些 $(l, r, h)$ 有贡献。

但更好的方法是：在 DP 中实时计算顾客数，使用前缀和优化。

更优的算法

由于 $n$ 很小，我们可以用 $O(n^3 \times K)$ 的算法，但 $K$ 可能达到 $4000$，$50^3 \times 4000 = 5 \times 10^8$，可能勉强通过（2.6秒时间限制）。

但实际实现时，可以通过剪枝优化。

总结

本题的核心：

1. 区间DP：枚举区间最小值的位置和值
2. 离散化：价格只取顾客的 $c_i$ 值
3. 顾客贡献计算：预处理或动态计算包含某位置的区间数量

算法复杂度较高，但利用 $n$ 小的特点，可以通过精心优化实现。