bzoj4380[POI2015]Myjnie dp

[POI2015]Myjnie

Time Limit: 40 Sec Memory Limit: 256 MBSec Special Judge
Submit: 368 Solved: 185
[Submit][Status][Discuss]

Description

有n家洗车店从左往右排成一排，每家店都有一个正整数价格p[i]。
有m个人要来消费，第i个人会驶过第a[i]个开始一直到第b[i]个洗车店，且会选择这些店中最便宜的一个进行一次消费。但是如果这个最便宜的价格大于c[i]，那么这个人就不洗车了。
请给每家店指定一个价格，使得所有人花的钱的总和最大。

Input

第一行包含两个正整数n,m(1<=n<=50，1<=m<=4000)。
接下来m行，每行包含三个正整数a[i],b[i],c[i](1<=a[i]<=b[i]<=n，1<=c[i]<=500000)

Output

第一行输出一个正整数，即消费总额的最大值。
第二行输出n个正整数，依次表示每家洗车店的价格p[i]，要求1<=p[i]<=500000。
若有多组最优解，输出任意一组。

Sample Input

7 5
1 4 7
3 7 13
5 6 20
6 7 1
1 2 5

Sample Output

43
5 5 13 13 20 20 13

HINT

Source

鸣谢Claris

出题人https://www.cnblogs.com/clrs97/p/5271139.html

ysy

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 
 7 #define N 55
 8 #define M 4007
 9 #define maxc 500007
10 using namespace std;
11 
12 int n,m;
13 int f[N][N][M],g[N][N][M],h[N][M];
14 int p[N][N][M],val[N];
15 int C[M],lsh[maxc],LSH[M],K;
16 
17 inline void up(int &x,const int &y)
18 {
19     if(x<y)x=y;
20 }
21 struct node
22 {
23     int a,b,c;
24 }a[M];
25 inline bool cmp(node x,node y)
26 {
27     return x.b==y.b?x.a<y.a:x.b<y.b;
28 }
29 void pre()
30 {
31     sort(a+1,a+m+1,cmp);
32 
33     sort(C+1,C+m+1); K=0;
34     for(int i=1;i<=m;i++)
35         if(C[i]!=C[i-1]) LSH[++K]=C[i],lsh[C[i]]=K;
36     for(int i=1;i<=m;i++) a[i].c=lsh[a[i].c];
37 }
38 void search(int l,int r,int k)
39 {
40     if(l>r) return ;
41     if(!g[l][r][k])
42     {
43         for(int i=l;i<=r;i++) val[i]=LSH[k];
44         return ;
45     }
46     for(int i=k;i<=K;i++) if(g[l][r][k]==f[l][r][i])
47     {
48         const int pos=p[l][r][i];
49         val[pos]=LSH[i];
50         search(l,pos-1,i); search(pos+1,r,i);
51         break;
52     }
53 }
54 int main()
55 {
56     scanf("%d%d",&n,&m);
57     for(int i=1;i<=m;i++) 
58         scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c),C[i]=a[i].c;
59     pre();
60     for(int l=n;l>=1;l--) 
61         for(int r=l;r<=n;r++)
62         {
63                for(int i=l;i<=r;i++) 
64                 for(int j=1;j<=K;j++) h[i][j]=0;
65             for(int i=1;i<=m&&a[i].b<=r;i++)
66             {
67                 if(a[i].a<l) continue;
68                 for(int j=a[i].a;j<=a[i].b;j++) 
69                     h[j][a[i].c]++;
70                }
71             for(int i=l;i<=r;i++) 
72                 for(int j=K-1;j>=1;j--) 
73                     h[i][j]+=h[i][j+1];
74             for(int i=l;i<=r;i++)
75                 for(int j=K;j>=1;j--)
76                 {
77                     int tmp=g[l][i-1][j]+g[i+1][r][j]+h[i][j]*LSH[j];
78                     if(f[l][r][j]<tmp) f[l][r][j]=tmp,p[l][r][j]=i;
79                     g[l][r][j]=g[l][r][j+1]>f[l][r][j]?g[l][r][j+1]:f[l][r][j];
80                 }
81            }
82     printf("%d
",g[1][n][1]);
83     search(1,n,1);
84     for(int i=1;i<=n;i++)
85         printf("%d ",val[i]);
86 }