【BZOJ 4380】4380: [POI2015]Myjnie （区间DP）

4380: [POI2015]Myjnie

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

【分析】

　　不会做这题，感觉我不会区间DP orz。。

　　orz Claris大神

　　额。。代码跟他写的好像不是很一样。

　　g是最大收益，f是取到最大收益的时候的选k的那个位置

　　还有一个p[i][j][k]表示[i][j][k...m]的[i][j][p[i][j][k]]时的收益最大

　　嗯。。g的继承和求p部分主要是加速的，重点是方程

　　g[i][j][k]=max(g[i][l-1][k]+g[l+1][j][k]+c[k]*h[x][k])

　　后面两个小区间的g已经是继承过的，所以真正表示的是区间[i][l-1]然后最小值>=k的最大收益

　　对这种DP不熟啊！！

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 #define Maxn 60
 8 #define Maxm 4010
 9 
10 int mymax(int x,int y) {return x>y?x:y;}
11 int mymin(int x,int y) {return x<y?x:y;}
12 
13 int f[Maxn][Maxn][Maxm],g[Maxn][Maxn][Maxm],p[Maxn][Maxn][Maxm];
14 int h[Maxn][Maxm];
15 int a[Maxm],b[Maxm],c[Maxm],id[Maxm];
16 
17 struct node {int x,y;}t[Maxm];
18 bool cmp(node x,node y) {return x.x<y.x;}
19 
20 int op[Maxn];
21 void output(int l,int r,int k)
22 {
23       if(l>r) return;
24       k=p[l][r][k];
25       int x=f[l][r][k];
26       op[x]=t[k].x;
27       output(l,x-1,k);output(x+1,r,k);
28 }
29 
30 int main()
31 {
32     int n,m;
33     scanf("%d%d",&n,&m);
34     for(int i=1;i<=m;i++)
35     {
36         scanf("%d%d%d",&a[i],&b[i],&c[i]);
37         t[i].x=c[i];t[i].y=i;
38     }
39     sort(t+1,t+1+m,cmp);
40     for(int i=1;i<=m;i++) id[t[i].y]=i;
41     memset(g,0,sizeof(g));
42     for(int i=n;i>=1;i--)
43      for(int j=i;j<=n;j++)
44      {
45          for(int k=i;k<=j;k++) for(int l=1;l<=m;l++) h[k][l]=0;
46          for(int k=1;k<=m;k++) if(i<=a[k]&&b[k]<=j) for(int l=a[k];l<=b[k];l++) h[l][id[k]]++;
47          for(int k=i;k<=j;k++) for(int l=m-1;l>=1;l--) h[k][l]+=h[k][l+1];
48          for(int k=m;k>=1;k--)
49          {
50              int mx=0;
51              for(int l=i;l<=j;l++)
52              {
53                  int nw;
54                  nw=g[i][l-1][k]+g[l+1][j][k]+h[l][k]*t[k].x;
55                  if(nw>=mx) mx=nw,f[i][j][k]=l;
56              }
57              if(mx>=g[i][j][k+1]) g[i][j][k]=mx,p[i][j][k]=k;
58              else g[i][j][k]=g[i][j][k+1],p[i][j][k]=p[i][j][k+1];
59          }
60      }
61     printf("%d
",g[1][n][1]);
62     output(1,n,1);
63     for(int i=1;i<=n;i++) printf("%d ",op[i]);
64     printf("
");
65     return 0;
66 }

View Code

2017-03-22 18:29:41