Description
有$n$家洗车店从左往右排成一排，每家店都有一个正整数价格$p[i]$。
有$m$个人要来消费，第$i$个人会驶过第$a[i]$个开始一直到第$b[i]$个洗车店，且会选择这些店中最便宜的一个进行一次消费。但是如果这个最便宜的价格大于$c[i]$，那么这个人就不洗车了。
请给每家店指定一个价格，使得所有人花的钱的总和最大。
Solution
神仙$DP$ QAQ
每个店的价格肯定是$c_i$中的某一个值， 所以可以离散化
定义状态 $dp[L][R][k]$ 表示 在区间$[i,j]$ 最小值为$k$ 时所能收益的最大值
转移 ： $dp[L][R][k] = \max{(dp[L][i - 1][k] + dp[i + 1][R][k] + cnt[i][k])}$
但是发现这样无法快速求出答案， 所以把$dp[L][R][k]$定义为 最小值 $>=k$时所能收益的最大值。
则多了一个转移： $dp[L][R][k] = \max{(dp[L][R][k], dp[L][R][k + 1])}$。
题目要求 求出方案， 则定义$val[L][R][k]$ 为真正的$k$值， $P[L][R][k]$ 为哪个位置取 $k$
最后递归求方案
空间复杂度$O(N^2M)$, 时间复杂度$O(N^3M)$
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 55
#define M 4005
#define rd read()
using namespace std; int n, m;
int dp[N][N][M], cnt[N][M], val[N][N][M], P[N][N][M];
int ls[M], tot, ans[N]; struct node {
int l, r, val;
}a[M]; inline int read() {
int X = , p = ; char c = getchar();
for (; c > '' || c < ''; c = getchar())
if (c == '-') p = -;
for (; c >= '' && c <= ''; c = getchar())
X = X * + c - '';
return X * p;
} int fd(int x) {
return lower_bound(ls + , ls + + tot, x) - ls;
} void cmax(int &A, int B) {
if (A < B)
A = B;
} void DP(int L, int R) {
memset(cnt, , sizeof(cnt));
for (int i = ; i <= m; ++i) {
if (a[i].l < L || a[i].r > R)
continue;
for (int j = a[i].l; j <= a[i].r; ++j)
cnt[j][a[i].val]++;
}
for (int i = L; i <= R; ++i)
for (int j = tot - ; j; --j)
cnt[i][j] += cnt[i][j + ];
for (int i = tot; i; --i) {
int maxn = -, pos = ;
for (int j = L; j <= R; ++j) {
int res = dp[L][j - ][i] + dp[j + ][R][i] + cnt[j][i] * ls[i];
if (res > maxn)
maxn = res, pos = j;
cmax(dp[L][R][i], res);
}
val[L][R][i] = i;
P[L][R][i] = pos;
if(i < m && dp[L][R][i] < dp[L][R][i + ])
val[L][R][i] = val[L][R][i + ],
dp[L][R][i] = dp[L][R][i + ],
P[L][R][i] = P[L][R][i + ];
}
} void findans(int L, int R, int lim) {
if (L > R) return;
int fin = val[L][R][lim], pos = P[L][R][lim];
ans[pos] = fin;
findans(L, pos - , fin);
findans(pos + , R, fin);
} int main()
{
n = rd; m = rd;
for (int i = ; i <= m; ++i) {
a[i].l = rd; a[i].r = rd; a[i].val = rd;
ls[++tot] = a[i].val;
}
sort(ls + , ls + + tot);
tot = unique(ls + , ls + + tot) - ls - ;
for (int i = ; i <= m; ++i)
a[i].val = fd(a[i].val);
for (int i = n; i; --i)
for (int j = i; j <= n; ++j)
DP(i, j);
printf("%d\n", dp[][n][]);
findans(, n, );
for (int i = ; i <= n; ++i)
printf("%d ", ls[ans[i]]);
puts("");
}