【斜率DP】BZOJ 1911:特别行动队

1911: [Apio2010]特别行动队

Time Limit: 4 Sec  Memory Limit: 64 MB
Submit: 3006  Solved: 1360
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

4
-1 10 -20
2 2 3 4

Sample Output

9

HINT

---

　　很容易写出斜率式什么的就不说了。。

　　不开long long见祖宗。。

　　

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<cstdio>

 #define maxn 1000001

 using namespace std;

 long long sum[maxn],f[maxn];

 int a,b,c,n,que[maxn],head=,tail=;

 double K(int x,int y){return (double)(sum[x]+sum[y])/2.0+(double)(f[y]-f[x])/(2.0*a*(sum[y]-sum[x]))-(double)b/(2.0*a);}

 long long F(int x){return a*x*x+b*x+c;}

 void DP()

 {

     que[tail]=;

     for(int i=;i<=n;i++)

     {

         while(head<tail && sum[i] >= K(que[head],que[head+]))head++;

         int sd=que[head];

         f[i]=f[sd]+F(sum[i]-sum[sd]);

         while(head<tail && K(que[tail],i) <= K(que[tail-],que[tail]))tail--;

         que[++tail]=i;

     }

     printf("%lld",f[n]);

 }

 int main()

 {

     scanf("%d%d%d%d",&n,&a,&b,&c);

     for(int i=;i<=n;i++)scanf("%lld",&sum[i]),sum[i]+=sum[i-];

     DP();

     return ;

 }