【JZOJ 4931】【NOIP2017提高组模拟12.24】A

时间:2021-09-15 20:46:20

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的人有多少个,
转移:
fl,r,k=max(gi,p1,k+gp+1,r,k+k(bl,r,kbl,P1,kbp+1,r,k))

复杂度: O(n3m)

我们要有梦想,要相信梦想和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;
}