题目描述
有 \(n\) 家洗车店从左往右排成一排，每家店都有一个正整数价格 \(p_i\)。有 \(m\) 个人要来消费，第 \(i\) 个人会驶过第 \(a_i\) 个开始一直到第 \(b_i\) 个洗车店，且会选择这些店中最便宜的一个进行一次消费。但是如果这个最便宜的价格大于 \(c_i\)，那么这个人就不洗车了。请给每家店指定一个价格，使得所有人花的钱的总和最大。
分析
固然，先对 \(c\) 离散化一下。另一方面，一眼发现该题是一个区间dp。
由题意可知，某个区间内的最小值是影响答案的关键元素，不妨先定义一下状态 \(dp[l][r][mn]\)，表示当区间 \([l,r]\) 内的最低价格为 \(mn\) 时在这个区间所能获得的最大收益。
那么，到现在为止，能完成转移吗？不太行。
原因是你无从得知究竟有多少车主在区间 \([l,r]\)会考虑洗车。而车主是否会洗车，又取决于该区间内的点的最小值与车主的期望值的关系。因此，不妨预处理出一个 \(cost[i][j]\)，表示如果第 \(i\) 家洗车店的价格为 \(j\)，会有多少个车主可能到这里洗车。
接下来，就需要在区间 \([l,r]\) 中枚举一个 \(k\)，令这家洗车店的价格为 \(mn\)，由此，就能将当前区间分成左右两个部分，这就体现出了笛卡尔树的感觉了（把你枚举的这个 \(k\) 当作树根，左右两个区间分别为左右子树，显然，左右两个区间的最小值都是大于或等于树根 \(k\) 对应的值 \(mn\) 的）。
总的dp方程就是：
\[dp[l][r][mn] = max(dp[l][r][mn],dp[l][k][x >= k] + dp[k + 1][r][y >= k] + k * cost[k][mn]) \]由于最后要求输出方案，转移的时候还需要记录一下某个区间对应的取 \(mn\) 时的 \(k\)，这点细节不太好处理。我的代码是直接用定义的 dp 数组来记录后缀max，因此在处理记录的决策信息时似乎有点抽象？烦读者自行理解。
另一方面，注意到，dp[l][k][x >= k] 和dp[k + 1][r][y >= k]这两个东西可以通过后缀取max优化掉，所以总的时间复杂度为 \(O(n^3m)\)。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 55;
vector<int> lsh;
int n,m,cost[MAXN + 5][4015],
dp[MAXN + 5][MAXN + 5][4015],f[MAXN + 5][MAXN + 5][4015],last[MAXN + 5][MAXN + 5][4015],out[MAXN + 5];
struct NPE{
int a,b,c;
}p[4005];
void print(int l,int r,int mmin){
if(l == 0 || r == 0)return;
if(l > r)return;
int k = f[l][r][mmin];
out[k] = last[l][r][mmin];
print(l,k - 1,last[l][r][mmin]);
print(k + 1,r,last[l][r][mmin]);
}
bool cmp(NPE a,NPE b){
return a.c < b.c;
}
signed main(){
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++){
for(int j = i; j <= n; j++){
for(int k = 1; k <= m; k++)dp[i][j][k] = -1;
}
}
for(int i = 1; i <= m; i++){
scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c);
}
sort(p + 1,p + 1 + m,cmp);
for(int len = 1; len <= n; len++){
for(int l = 1; l + len - 1 <= n; l++){
int r = len + l - 1;
for(int i = l; i <= r; i++){
for(int j = 1; j <= m; j++){
cost[i][j] = 0;
}
}
for(int j = 1; j <= m; j++){
if(p[j].a >= l && p[j].b <= r){
for(int i = p[j].a; i <= p[j].b; i++){
cost[i][j]++;
}
}
}
for(int i = l; i <= r; i++){
for(int j = m; j; j--){
cost[i][j] += cost[i][j+1];
}
}
for(int k = l; k <= r; k++){
for(int mmin = 1; mmin <= m; mmin++){
if(dp[l][r][mmin] < dp[l][k-1][mmin] + dp[k + 1][r][mmin] + p[mmin].c * cost[k][mmin]){
dp[l][r][mmin] = dp[l][k-1][mmin] + dp[k + 1][r][mmin] + p[mmin].c * cost[k][mmin];
f[l][r][mmin] = k;
last[l][r][mmin] = mmin;
}
}
}
for(int mmin = m; mmin >= 1; mmin--){
if(dp[l][r][mmin] < dp[l][r][mmin + 1]){
dp[l][r][mmin] = max(dp[l][r][mmin],dp[l][r][mmin + 1]);
f[l][r][mmin] = f[l][r][mmin + 1];
last[l][r][mmin] = last[l][r][mmin + 1];
}
}
}
}
print(1,n,1);
cout << dp[1][n][1] << "\n";
for(int i = 1; i <= n; i++){
cout << p[out[i]].c << " ";
}
}