Rockdu's Blog

题目描述

有n家洗车店从左往右排成一排，每家店都有一个正整数价格p[i]。有m个人要来消费，第i个人会驶过第a[i]个开始一直到第b[i]个洗车店，且会选择这些店中最便宜的一个进行一次消费。但是如果这个最便宜的价格大于c[i]，那么这个人就不洗车了。请给每家店指定一个价格，使得所有人花的钱的总和最大。

输入输出格式

输入格式：

第一行包含两个正整数n,m(1<=n<=50，1<=m<=4000)。接下来m行，每行包含三个正整数a[i],b[i],ci

输出格式：

第一行输出一个正整数，即消费总额的最大值。第二行输出n个正整数，依次表示每家洗车店的价格p[i]，要求1<=p[i]<=500000。若有多组最优解，输出任意一组。

输入输出样例

7 5
1 4 7
3 7 13
5 6 20
6 7 1
1 2 5

43
5 5 13 13 20 20 13

说明

有n家洗车店从左往右排成一排，每家店都有一个正整数价格p[i]。

有m个人要来消费，第i个人会驶过第a[i]个开始一直到第b[i]个洗车店，且会选择这些店中最便宜的一个进行一次消费。但是如果这个最便宜的价格大于c[i]，那么这个人就不洗车了。

请给每家店指定一个价格，使得所有人花的钱的总和最大。

这题在雅礼讲过，自己还想那么久，太菜了……

对于这道题n=50那就是复杂度是次要的，有做法基本就能过。

我们思考一个区间DP，用dp[l][r][k]表示处理完l, r区间内最小值为k的最大盈利。实际上我们通过限制转移顺序就可以转移这个比较科学的状态了。我们只要在每次只处理：要选择的区间在当前枚举的l, r内的顾客，转移就好办了。但是这样复杂度不够优，我们可以记最小值大于等于k的最大盈利，这样时间复杂度为O(n^3*m)，还是略卡。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define For(i, a, b) for(register int i = a; i <= b; ++i)
#define Down(i, a, b) for(register int i = a; i >= b; --i)
using namespace std;
const int maxn = 55, maxm = 4e3 + 5;
int dp[maxn][maxn][maxm], mx[maxn][maxn][maxm], n, m;
int c[maxm], tmp[maxm], rk[maxm], l, r, tot[maxn], tp;
int frm[maxn][maxn][maxm], pi, ans;
struct Q {
    int l, r, c;
    bool operator <(const Q &A) const {
        return c < A.c;
    }
}qs[maxm];

void CG(int x) {
    For(i, qs[x].l, qs[x].r) ++tot[i];
}

int ret[maxn];
void prt(int l, int r, int k) {
    if(l > r) return ;
    int mid = dp[l][r][k];
    prt(l, mid - 1, frm[l][mid - 1][k]);
    ret[mid] = tmp[k];
    prt(mid + 1, r, frm[mid + 1][r][k]);
}

int main() {
    
    scanf("%d%d", &n, &m);
    For(i, 1, m) {
        scanf("%d%d%d", &qs[i].l, &qs[i].r, &qs[i].c);
        tmp[i] = qs[i].c;
    }
    sort(tmp + 1, tmp + m + 1);
    For(i, 1, m) if(tmp[i] != tmp[i - 1]) 
    rk[i] = rk[i - 1] + 1; else rk[i] = rk[i - 1];
    sort(qs + 1, qs + m + 1);
    For(i, 1, m) qs[i].c = rk[i];
    tmp[0] = unique(tmp + 1, tmp + m + 1) - tmp - 1;
    tp = m;
    For(len, 0, n - 1) {
        For(x, 1, n - len) {
            l = x, r = x + len, tp = m;
            memset(tot, 0, sizeof(tot));
            Down(i, tmp[0], 1) {
                while(qs[tp].c == i){
                    if(qs[tp].l >= l && qs[tp].r <= r) CG(tp);
                    --tp;
                } 
                pi = 0, ans = 0;
                For(mid, l, r)
                    if(ans <= mx[l][mid - 1][i] + mx[mid + 1][r][i] + tmp[i] * tot[mid])
                        pi = mid, ans = mx[l][mid - 1][i] + mx[mid + 1][r][i] + tmp[i] * tot[mid];
                mx[l][r][i] = mx[l][r][i + 1];
                dp[l][r][i] = pi;
                frm[l][r][i] = frm[l][r][i + 1];
                if(mx[l][r][i] <= ans) mx[l][r][i] = ans, frm[l][r][i] = i;
            }
        }
    }
    printf("%d\n", mx[1][n][1]);
    prt(1, n, frm[1][n][1]);
    For(i, 1, n) printf("%d ", ret[i]);
    return 0;
}