单调栈 BZOJ2364 城市美化

2364: 城市美化

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 182 Solved: 42
[Submit][Status][Discuss]

Description

城市A需要美化市容市貌，现在有n个楼房排成一列，每个楼房的高都在[1,1000]的范围内。市长请了一批工程师来对其中一些楼房进行修建，使楼房高度得到上升（不能让楼房高度下降），对一栋楼房修建，使其高度上升x，需要x²的费用。

当所有修建完成后，我们把相邻两楼高度的绝对值乘以c(0<=c<=1000)，得到的就是城市损失的钱，我们把它同样看作是费用。现在想请你合理安排修建楼房的方案，使得所需费用最小。

Input

第一行两个数n和c。

接下来n行，每行一个数，表示每栋楼的高度。

Output

仅一行一个数，表示最小所需的费用。

Sample Input

5 5
2
2
1
6
8

Sample Output

HINT

数据范围

对于100%的数据，1<=n<=50000

f[i]表示前i个且最后一段与 i-1 相同的最小代价。

可以得到一些性质：(1) 当一个楼房两边都比它高，或者一个楼房处于边界，那么将它向上调整才能使代价减小；

　　　　　　　　　(2) 若一个楼房两边都高于它，且最后它向上调整了，则两侧的楼房高度都应与它相同，直到有比它更高的为止。

则可以维护一个单调递减的楼房转移，ask用于二次函数求极值。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 int n,c,top;
 8 int stack[50010];
 9 long long h[50010],sum[50010],sumpow[50010],f[50010];
10 long long ask(long long a,long long b,long long d,long long mn,long long mx){
11     double t=(double)-b/(2*a);
12     long long x;
13     if(mn<=t&&t<=mx) x=round(t);
14     if(mn>t) x=mn;
15     if(mx<t) x=mx;
16     return a*x*x+b*x+d; 
17 }
18 long long solve(int ll,int rr,long long mn){
19     if(ll+1==rr) return (ll==1||rr==n+2)?0:abs(h[rr]-h[ll])*c;
20     long long a=rr-ll-1,b=-2*(sum[rr-1]-sum[ll]),d=sumpow[rr-1]-sumpow[ll];
21     long long mx=min(h[ll],h[rr]);
22     if(ll!=1) b-=c,d+=c*h[ll];
23     if(rr!=n+2) b-=c,d+=c*h[rr];
24     return ask(a,b,d,mn,mx);
25 }
26 long long work(){
27     stack[++top]=1;
28     for(int i=2;i<=n+2;i++){
29         f[i]=1e60;
30         int end=0;
31         while(top&&h[stack[top]]<h[i]){
32             f[i]=min(f[i],f[stack[top]]+solve(stack[top],i,end));
33             end=h[stack[top--]];
34         }
35         f[i]=min(f[i],f[stack[top]]+solve(stack[top],i,end));
36         stack[++top]=i;
37     } 
38     return f[n+2];
39 }
40 int main(){
41     scanf("%d%d",&n,&c);
42     h[1]=h[n+2]=1e60;
43     for(int i=1;i<=n;i++) scanf("%d",&h[i+1]);
44     for(int i=1;i<=n+2;i++){
45         sum[i]=sum[i-1]+h[i];
46         sumpow[i]=sumpow[i-1]+h[i]*h[i];
47     }
48     printf("%lld",work());
49     return 0;
50 }