特别行动队[APIO2010]

题目传送门

1911: [Apio2010]特别行动队

Time Limit: 4 Sec Memory Limit: 64 MB
Submit: 5349 Solved: 2651
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

4
-1 10 -20
2 2 3 4

Sample Output

HINT

Source

[Submit][Status][Discuss]

　　斜率优化dp

　　不过需要注意的是这道题斜率是负的，并且维护的是个上凸包。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #define LL long long
 7 using namespace std ;
 8 const int N = 1e6 + 10 ;
 9 
10 inline LL read() {
11     LL k = 0, f = 1 ; char c = getchar() ;
12     for( ; !isdigit(c) ; c = getchar())
13       if(c == '-') f = -1 ;
14     for( ; isdigit(c) ; c = getchar())
15       k = k*10 + c-'0' ;
16     return k*f ;
17 } 
18 int n ; LL a, b, c ; LL pp[N] ;
19 int q[N] ; LL f[N] ;
20 
21 inline LL sqr(LL x) { return x*x ; }
22 inline double Y(int i) { return f[i]+a*sqr(pp[i])-b*pp[i] ; }
23 inline double X(int i) { return pp[i] ; }
24 inline double Rate(int i,int j) { return (Y(j)-Y(i))/(X(j)-X(i)) ; }
25 
26 int main() {
27     n = read() ; a = read(), b = read(), c = read() ;
28     for(int i=1;i<=n;i++) pp[i] = pp[i-1]+read() ;
29     int head = 1, tail = 1 ; q[1] = 0 ;
30     for(int i=1;i<=n;i++) {
31         while(head < tail && Rate(q[head],q[head+1]) > (double)2*a*pp[i]) head++ ;
32         int j = q[head] ; f[i] = f[j]+a*sqr(pp[i]-pp[j])+b*(pp[i]-pp[j])+c ;
33         while(head < tail && Rate(q[tail-1],q[tail]) < Rate(q[tail],i)) tail-- ;
34         q[++tail] = i ;
35     }
36     printf("%lld",f[n]) ;
37     return 0 ;
38 }