[POI2015]Myjnie

Time Limit: 40 Sec  Memory Limit: 256 MBSec  Special Judge

Submit: 368  Solved: 185

[][][]

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

 

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

ysy 

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6  7 #define N 55 8 #define M 4007 9 #define maxc 50000710 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
           
            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
            
             =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]
             
              f[l][r][j]?g[l][r][j+1]:f[l][r][j];80 }81 }82 printf("%d\n",g[1][n][1]);83 search(1,n,1);84 for(int i=1;i<=n;i++)85 printf("%d ",val[i]);86 }