dsy1010: [HNOI2008]玩具裝箱

【題目描述】

有n個(gè)數(shù)，分成連續(xù)的若干段，每段（假設(shè)從第j個(gè)到第i個(gè)組成一段）的分?jǐn)?shù)為?(X-L)^2，X為j-i+Sigma(Ck) i<=k<=j，其中L是一個(gè)常量。目標(biāo)：各段分?jǐn)?shù)的總和最小。

【輸入格式】

第一行：兩個(gè)整數(shù)N，L.下來(lái)N個(gè)數(shù)字Ci.1<=N<=50000,1<=L,Ci<=10^7

【輸出格式】

一個(gè)整數(shù)，各段分?jǐn)?shù)總和的值最小。

Sample Input

5 4

3?4?2?1?4

Sample Output

1

?

維護(hù)一個(gè)右下凸包。

?

1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<cmath> 5 #include<iostream> 6 #include<algorithm> 7 #include<queue> 8 using namespace std; 9 10 typedef long long LL; 11 const LL N=50010; 12 LL n,L,NL,f[N],sum[N],s[N],Q[N]; 13 14 // f[i]=a[i]*x[j]+b[j] 15 // LL=L+1 16 // a[i]=-2*(s[i]-LL) 17 // x[j]=s[j] 18 // b[j]=f[j]+s[j]^2 19 20 double X(LL i){return s[i];} 21 double Y(LL i){return f[i]+s[i]*s[i];} 22 double find_k(LL i,LL j){return (Y(j)-Y(i))/(X(j)-X(i));} 23 24 int main() 25 { 26 // freopen("a.in","r",stdin); 27 freopen("toy.in","r",stdin); 28 freopen("toy.out","w",stdout); 29 scanf("%lld%lld",&n,&L); 30 sum[0]=0;s[0]=0;NL=L+1; 31 for(int i=1;i<=n;i++) 32 { 33 LL x; 34 scanf("%lld",&x); 35 sum[i]=sum[i-1]+x; 36 } 37 for(int i=1;i<=n;i++) s[i]=sum[i]+i; 38 // for(LL i=1;i<=n;i++) printf("%d ",sum[i]);printf("\n"); 39 // for(LL i=1;i<=n;i++) printf("%d ",s[i]);printf("\n"); 40 LL l=0,r=0,j,ai,xj,bj,ti; 41 double k; 42 memset(f,0,sizeof(f)); 43 for(int i=1;i<=n;i++) 44 { 45 ai=(-2)*(s[i]-NL); 46 while(l<r && find_k(Q[l],Q[l+1])<=(-ai) ) l++; 47 j=Q[l]; 48 xj=s[j]; 49 bj=f[j]+s[j]*s[j]; 50 ti=(s[i]-NL)*(s[i]-NL); 51 f[i]=ai*xj+bj+ti; 52 while(l<r && find_k(Q[r],Q[r-1])>find_k(i,Q[r])) r--; 53 Q[++r]=i; 54 } 55 printf("%lld\n",f[n]); 56 return 0; 57 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/KonjakJuruo/p/5890581.html

總結(jié)

以上是生活随笔為你收集整理的【bzoj1010-toy】斜率优化入门模板的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。