Description
有N家洗车店从左往右排成一排，每家店都有一个正整数价格Pi。
有M个人要来消费，第i个人会驶过第Ai个开始一直到第Bi个洗车店，且会选择这些店中最便宜的一个进行一次消费。但是如果这个最便宜的价格大于Ci，那么这个人就不洗车了。
请给每家店指定一个价格，使得所有人花的钱的总和最大。
Data Constraint
所有数据满足N<=50,M<=4000,1<=Ai<=Bi<=N,1<=Ci<=500000
Solution
这道题，脑补了半天愣是……
正解是这样：我们先将ci离散化，设f[l][r][x]表示在[l,r]的洗车店之间的最小价格为x的最大代价。那么现在枚举一个p，表示最小价格所在的洗车店为p。那么
我们先来讨论怎样解决怎样解决方程中的x1,x2。显然，我们可以修改一下f[l][r][x]的定义，设f[l][r][x]表示在[l,r]的洗车店之间的最小价格至少为x的最大代价。那么式子就变成
我们再来讨论怎样计算tot.我们设g[p][x]表示左右端点均在[l,r]且跨越p在p为x时的人的贡献。我们可以枚举一下这n个顾客，当一个顾客的左右端点均在[l,r]时我们枚举这个人经历的点x，并在g[x][c[i]]处+1。最后只要把g[x][j+1]的值加到g[x][j]处即可。
所以最后式子成了
总时间复杂度O(
Code
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=4005,mo=5e5+5;
int a[maxn],b[maxn],c[maxn],d[maxn],q[mo],p1[maxn],f[55][55][maxn],g[55][maxn];
int n,m,i,t,j,k,l,ans,num,x,y,z,p,r;
int main(){
// freopen("data.in","r",stdin);
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
scanf("%d%d%d",&a[i],&b[i],&c[i]),d[i]=c[i];
sort(d+1,d+m+1);
for (i=1;i<=m;i++)
if (d[i]!=d[i-1]) q[d[i]]=++num,p1[num]=d[i];
for (i=1;i<=n;i++){
for (l=1;l<=n-i+1;l++){
r=l+i-1;
memset(g,0,sizeof(g));
for (j=1;j<=m;j++){
if (a[j]<l || b[j]>r) continue;
for (x=a[j];x<=b[j];x++)
g[x][q[c[j]]]++;
}
for (j=l;j<=r;j++)
for (k=num-1;k>=1;k--)
g[j][k]+=g[j][k+1];
for (p=l;p<=r;p++)
for (x=1;x<=num;x++)
f[l][r][x]=max(f[l][r][x],f[l][p-1][x]+f[p+1][r][x]+g[p][x]*p1[x]);
for (x=num-1;x>=1;x--)
f[l][r][x]=max(f[l][r][x],f[l][r][x+1]);
}
}
printf("%d\n",f[1][n][1]);
}