Description
有N家洗车店从左往右排成一排，每家店都有一个正整数价格Pi。
有M个人要来消费，第i个人会驶过第Ai个开始一直到第Bi个洗车店，且会选择这些店中最便宜的一个进行一次消费。但是如果这个最便宜的价格大于Ci，那么这个人就不洗车了。
请给每家店指定一个价格，使得所有人花的钱的总和最大。
本题开O2
Solution
本题为区间DP，
设f[l,r,k]表示l~r这个区间内，最小值为k的所有被包含在这个区间内的人的最大的消费，
转移时我们可以在l~r中枚举一个点p作为最小的那个点，设g[l,r,k]表示max(f[l,r,k~m])，b[l,r,k]表示在l~r这个区间内的并且C>=k的人有多少个，
转移：
复杂度：
我们要有梦想，要相信梦想和O2的力量！
Code
祝大家卡常愉快！
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define max(q,w) ((q)>(w)?(q):(w))
using namespace std;
const int N=52,M=4005;
int read(int &n)
{
char ch=' ';int q=0,w=1;
for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
if(ch=='-')w=-1,ch=getchar();
for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;
}
int n,m,ans;
int b[N][N][M];
int f[N][N][M];
int ls[M],mx[N][N];
struct qqww{int x,y,v;}sc[2*N*N];
bool PX(qqww q,qqww w){return q.v<w.v;}
int main()
{
int q,r;
read(n),read(m);
fo(i,1,m)read(sc[i].x),read(sc[i].y),read(sc[i].v);
sort(sc+1,sc+1+m,PX);
q=0;
fo(i,1,m)
{
if(ls[q]!=sc[i].v)ls[++q]=sc[i].v;
fo(j,1,sc[i].x)fo(k,sc[i].y,n)b[j][k][q]++,mx[j][k]=max(mx[j][k],q);
}
fod(I,m-1,1)fo(i,1,n)fo(j,i,n)b[i][j][I]+=b[i][j][I+1];
fo(I,0,n-1)
fo(i,1,n-I)
{
r=i+I;
fod(j,mx[i][r],1)
{
f[i][r][j]=f[i][r][j+1];
fo(k,i,r)
f[i][r][j]=max(f[i][r][j],f[i][k-1][j]+f[k+1][r][j]+ls[j]*(b[i][r][j]-b[i][k-1][j]-b[k+1][r][j]));
}
}
ans=0;
fo(i,1,m)ans=max(ans,f[1][n][i]);
printf("%d\n",ans);
return 0;
}