bzoj 3156 防御准备（斜率DP）

3156: 防御准备

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 837 Solved: 395
[Submit][Status][Discuss]

Description

Input

第一行为一个整数N表示战线的总长度。

第二行N个整数，第i个整数表示在位置i放置守卫塔的花费Ai。

Output

共一个整数，表示最小的战线花费值。

Sample Input

10
2 3 1 5 4 5 6 3 1 2

Sample Output

HINT

1<=N<=10^6,1<=Ai<=10^9

Source

Katharon+#1

【思路】

斜率优化DP。

唯一需要注意的是过程中数据超范围，需要特别声明一下。

　　为毛斜率DP都长一个样<_<

【代码1】

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 
 5 typedef long long LL; 
 6 const int N = 1e6+10;
 7 struct point { LL x,y;
 8 }q[N],now;
 9 int n,L,R,a[N];
10 
11 LL cross(point a,point b,point c) {
12     return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
13 }
14 void read(int& x) {
15     char c=getchar(); while(!isdigit(c)) c=getchar();
16     x=0; while(isdigit(c)) x=x*10+c-'0' , c=getchar();
17 }
18 int main() {
19     //freopen("in.in","r",stdin);
20     //freopen("out.out","w",stdout);
21     read(n); 
22     for(int i=1;i<=n;i++) read(a[i]);
23     for(int i=1;i<=n;i++) {
24         while(L<R && q[L].y-q[L].x*i >= q[L+1].y-q[L+1].x*i) L++;
25         now.x=i;
26         now.y=q[L].y-(LL)q[L].x*i+(LL)i*i+a[i];
27         while(L<R && cross(q[R-1],q[R],now)<=0) R--;
28         q[++R]=now;
29     }
30     printf("%lld",q[R].y-(LL)n*(n+1)/2);    // (LL) n*(n+1)/2
31     return 0;
32 }

Folding 1

【代码2】

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 
 6 typedef long long LL;
 7 const int N = 1e6+10;
 8 
 9 int n,L,R,a[N],q[N]; LL f[N]; 
10 
11 double slop(int k,int j) {
12     return (double)(f[j]-f[k]+(LL)j*(j+1)/2-(LL)k*(k+1)/2)/(j-k);
13 }
14 void read(int& x) {
15     char c=getchar(); while(!isdigit(c)) c=getchar();
16     x=0; while(isdigit(c)) x=x*10+c-'0' , c=getchar();
17 }
18 int main() {
19     //freopen("in.in","r",stdin);
20     //freopen("out.out","w",stdout);
21     read(n);
22     for(int i=1;i<=n;i++) read(a[i]);
23     for(int i=1;i<=n;i++) {
24         while(L<R && slop(q[L],q[L+1])<i) L++;
25         int t=q[L];
26         f[i]=f[t]+(LL)i*(i-t)+(LL)t*(t+1)/2-(LL)i*(i+1)/2+a[i];
27         while(L<R && slop(q[R-1],q[R])>slop(q[R],i)) R--;
28         q[++R]=i;
29     }
30     printf("%lld",f[n]);
31     return 0;
32 }

Folding 2