首页 > 代码库 > Bzoj1911 [Apio2010]特别行动队
Bzoj1911 [Apio2010]特别行动队
1911: [Apio2010]特别行动队
Time Limit: 4 Sec Memory Limit: 64 MBSubmit: 3969 Solved: 1873
Description
Input
Output
Sample Input
4
-1 10 -20
2 2 3 4
-1 10 -20
2 2 3 4
Sample Output
9
HINT
Source
斜率优化DP
f[分组末尾]=最优解
f[i] = max{f[j]+A(s[i]-s[j])^2+B(s[i]-s[j])+C} (0<=j<i) (s[]是战斗力前缀和)
对于任意两个决策点j>k，假设j比k更优，则有：
f[j]+A(s[i]-s[j])^2+B(s[i]-s[j])+C >= f[k]+A(s[i]-s[k])^2+B(s[i]-s[k])+C
设G(j)=f[j]+A*s[j]^2-B*s[j] ，H(j)=-2*A*s[j]
由于H(j)>H(k)，得到[G(j)-G(k)]/[H(j)-H(k)]>=-s[i]
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #define LL long long 8 using namespace std; 9 const int mxn=1e6+10;10 int read(){11 int x=0,f=1;char ch=getchar();12 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14 return x*f;15 }16 LL f[mxn];17 int n;18 int a,b,c;19 int x[mxn];20 LL s[mxn];21 LL gdp(int i,int x){22 return f[x]+a*(s[i]-s[x])*(s[i]-s[x])+b*(s[i]-s[x])+c;23 }24 LL gup(int x,int y){25 return f[x]-f[y]+a*(s[x]*s[x]-s[y]*s[y])-b*(s[x]-s[y]);26 }27 LL gdown(int x,int y){28 return -2*a*s[x]+2*a*s[y];29 }30 int hd=0,tl=0;31 int q[mxn];32 int main(){33 n=read();34 a=read();b=read();c=read();35 int i,j;36 for(i=1;i<=n;i++){37 x[i]=read();38 s[i]=s[i-1]+x[i];39 }40 for(i=1;i<=n;i++){41 while(hd<tl && gup(q[hd],q[hd+1])<=-s[i]*gdown(q[hd],q[hd+1]))hd++;42 f[i]=gdp(i,q[hd]);43 while(hd<tl && gup(q[tl],i)*gdown(q[tl-1],q[tl])>=gup(q[tl-1],q[tl])*gdown(q[tl],i))tl--;44 q[++tl]=i;45 }46 printf("%lld\n",f[n]);47 return 0;48 }
Bzoj1911 [Apio2010]特别行动队
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。