网站 美食频道 建设,台州网站建设公司.,利用wordpress实现分类筛选,看设计比较好的网站dsy1010: [HNOI2008]玩具装箱 【题目描述】 有n个数#xff0c;分成连续的若干段#xff0c;每段#xff08;假设从第j个到第i个组成一段#xff09;的分数为 (X-L)^2#xff0c;X为j-iSigma(Ck) ikj#xff0c;其中L是一个常量。目标#xff1a;各段分数的总和…dsy1010: [HNOI2008]玩具装箱 【题目描述】 有n个数分成连续的若干段每段假设从第j个到第i个组成一段的分数为 (X-L)^2X为j-iSigma(Ck) ikj其中L是一个常量。目标各段分数的总和最小。 【输入格式】 第一行两个整数NL.下来N个数字Ci.1N50000,1L,Ci10^7 【输出格式】 一个整数各段分数总和的值最小。 Sample Input 5 4 3 4 2 1 4 Sample Output 1 维护一个右下凸包。 1 #includecstdio2 #includecstdlib3 #includecstring4 #includecmath5 #includeiostream6 #includealgorithm7 #includequeue8 using namespace std;9
10 typedef long long LL;
11 const LL N50010;
12 LL n,L,NL,f[N],sum[N],s[N],Q[N];
13
14 // f[i]a[i]*x[j]b[j]
15 // LLL1
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;NLL1;
31 for(int i1;in;i)
32 {
33 LL x;
34 scanf(%lld,x);
35 sum[i]sum[i-1]x;
36 }
37 for(int i1;in;i) s[i]sum[i]i;
38 // for(LL i1;in;i) printf(%d ,sum[i]);printf(\n);
39 // for(LL i1;in;i) printf(%d ,s[i]);printf(\n);
40 LL l0,r0,j,ai,xj,bj,ti;
41 double k;
42 memset(f,0,sizeof(f));
43 for(int i1;in;i)
44 {
45 ai(-2)*(s[i]-NL);
46 while(lr find_k(Q[l],Q[l1])(-ai) ) l;
47 jQ[l];
48 xjs[j];
49 bjf[j]s[j]*s[j];
50 ti(s[i]-NL)*(s[i]-NL);
51 f[i]ai*xjbjti;
52 while(lr 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 } 转载于:https://www.cnblogs.com/KonjakJuruo/p/5890581.html
