「BZOJ2364」城市美化
Description
城市A需要美化市容市貌，现在有n个楼房排成一列，每个楼房的高都在[1,1000]的范围内。市长请了一批工程师来对其中一些楼房进行修建，使楼房高度得到上升（不能让楼房高度下降），对一栋楼房修建，使其高度上升x，需要x2的费用。
当所有修建完成后，我们把相邻两楼高度的绝对值乘以c(0<=c<=1000)，得到的就是城市损失的钱，我们把它同样看作是费用。现在想请你合理安排修建楼房的方案，使得所需费用最小。
Input
第一行两个数n和c。
接下来n行，每行一个数，表示每栋楼的高度。
Output
仅一行一个数，表示最小所需的费用。
Sample Input
5 5
2
2
1
6
8
2
2
1
6
8
Sample Output
31
HINT
数据范围
对于100%的数据，1<=n<=50000
题解
这道题原题数据范围是100w。。。
用f[i]表示前i个，且最后一段与i-1相同的最小代价
可以得到一些性质。。
仅当一个楼房两边都比它高，或者一个楼房处于边界，那么将它向上调整才有可能使代价减小
如果一个楼房两边都高于它，且最后它向上调整了，则两侧的楼房高度都应与它相同，直到有比它更高的为止
那么只要维护一个单调递减，每个为止x仅能从x-上一个比x高的楼房y之间转移
f[x]=min { f[i]+cal（i,x）}
而cal（i，x）这是个二次函数求极值问题。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #define inf 1000000000000000000LL #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,C,top; int s[1000005]; ll sum[1000005],pow_sum[1000005],h[1000005]; ll f[1000005]; ll calf(ll a,ll b,ll c,ll l,ll r) { double t=(double)-b/(a*2); ll x; if(l<=t&&t<=r)x=round(t); if(l>t)x=l; if(r<t)x=r; return a*x*x+b*x+c; } ll cal(int l,int r,ll mn) { if(l+1==r)return (l==1||r==n+2)?0:abs(h[r]-h[l])*C; ll a=r-l-1,b=-2*(sum[r-1]-sum[l]),c=pow_sum[r-1]-pow_sum[l]; ll mx=min(h[l],h[r]); if(l!=1) b-=C,c+=C*h[l]; if(r!=n+2) b-=C,c+=C*h[r]; return calf(a,b,c,mn,mx); } ll solve() { s[++top]=1; for(int i=2;i<=n+2;i++) { f[i]=inf; int last=0; while(top&&h[s[top]]<h[i]) { f[i]=min(f[i],f[s[top]]+cal(s[top],i,last)); last=h[s[top--]]; } f[i]=min(f[i],f[s[top]]+cal(s[top],i,last)); s[++top]=i; } return f[n+2]; } int main() { n=read();C=read(); for(int i=1;i<=n;i++) h[i+1]=read(); h[1]=h[n+2]=inf; for(int i=1;i<=n+2;i++) { sum[i]=sum[i-1]+h[i]; pow_sum[i]=pow_sum[i-1]+h[i]*h[i]; } printf("%lld",solve()); return 0; } |
计数器 9793085
OI 课件=>
OI 课件=>
能不能解释一下求极值这个函数、、
额二次函数对称轴。。。
谢谢。。。我已经知道了。。。Orz学长