bzoj 1911 [Apio2010]特别行动队(斜率优化+DP)

1911: [Apio2010]特别行动队

Time Limit: 4 Sec  Memory Limit: 64 MB
Submit: 3191  Solved: 1450
[Submit][Status][Discuss]

Description

bzoj 1911 [Apio2010]特别行动队(斜率优化+DP)

Input

bzoj 1911 [Apio2010]特别行动队(斜率优化+DP)

Output

bzoj 1911 [Apio2010]特别行动队(斜率优化+DP)

Sample Input

4
-1 10 -20
2 2 3 4

Sample Output

9

HINT

bzoj 1911 [Apio2010]特别行动队(斜率优化+DP)

Source

【思路】

斜率优化。

设f[i]表示将前i个分组的最优值,则有转移方程式:

f[i]=max{ f[j]+a*(C[i]-C[j])^2+b*(C[i]-C[j])+c }

经过化简得到:

f[i]=max{ (f[j]+a*C[j]^2-b*C[j])-2*a*C[i]*C[j] } + a*C[i]^2+b*C[i]+c

单调队列维护上凸包即可。

【代码】

 #include<cstdio>
#include<iostream>
using namespace std; typedef long long LL;
const int N = +;
struct point { LL x,y;
}q[N],now;
int n,a,b,c,L,R; LL C[N]; LL cross(point a,point b,point c) {
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
void read(LL& x) {
char c=getchar(); while(!isdigit(c)) c=getchar();
x=; while(isdigit(c)) x=x*+c-'' , c=getchar();
}
int main() {
scanf("%d%d%d%d",&n,&a,&b,&c);
for(int i=;i<=n;i++)
read(C[i]) , C[i]+=C[i-];
for(int i=;i<=n;i++) {
while(L<R && q[L].y-*a*C[i]*q[L].x <= q[L+].y-*a*C[i]*q[L+].x) L++;
now.x=C[i];
now.y=q[L].y-*a*C[i]*q[L].x+*a*C[i]*C[i]+c;
while(L<R && cross(q[R-],now,q[R])<=) R--;
q[++R]=now;
}
printf("%lld",q[R].y+b*C[n]-a*C[n]*C[n]);
return ;
}
上一篇:Eclipse中Maven插件配置


下一篇:bzoj1911[Apio2010]特别行动队 斜率优化dp