首页 > > 程序设计 > C/C++ >

bzoj1911 [ APIO2010 ] -- 斜率优化

2018-06-17 23:14:38来源：未知阅读 ()

简单的斜率优化。

首先得到DP方程:

f[i]=max(f[j]+a*(sum[i]-sum[j])²+b*(sum[i]-sum[j])+c),j<i

其中sum表示前缀和

设j比k优

f[j]+a*(sum[i]-sum[j])²+b*(sum[i]-sum[j])+c>f[k]+a*(sum[i]-sum[k])²+b*(sum[i]-sum[k])+c

f[j]+a*s[j]²-b*s[j]-(f[k]+a*s[k]²-b*s[k])>2*a*s[i]*(s[j]-s[k])

然后就可以斜率优化了。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define N 1000010
 6 #define ll long long
 7 inline char nc(){
 8     static char buf[100000],*p1=buf,*p2=buf;
 9     if(p1==p2){
10         p2=(p1=buf)+fread(buf,1,100000,stdin);
11         if(p1==p2)return EOF;
12     }
13     return *p1++;
14 }
15 inline void Read(int& x){
16     char c=nc(),b=1;
17     for(;c<'0'||c>'9';c=nc())if(c=='-')b=-1;
18     for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=nc());x*=b;
19 }
20 inline void Read(ll& x){
21     char c=nc(),b=1;
22     for(;c<'0'||c>'9';c=nc())if(c=='-')b=-1;
23     for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=nc());x*=b;
24 }
25 ll y[N],f[N],s[N],k,a,b,c;
26 int i,j,n,m,ch[N],Top,A;
27 int main()
28 {
29     Read(n);Read(a);Read(b);Read(c);
30     for(i=1;i<=n;i++)Read(A),s[i]=s[i-1]+A;
31     for(i=1;i<=n;i++){
32         k=(a<<1)*s[i];
33         while(j<Top&&k*(s[ch[j+1]]-s[ch[j]])<=y[ch[j+1]]-y[ch[j]])j++;
34         f[i]=f[ch[j]]+a*(s[i]-s[ch[j]])*(s[i]-s[ch[j]])+b*(s[i]-s[ch[j]])+c;
35         y[i]=f[i]+a*s[i]*s[i]-b*s[i];
36         while(Top>j&&(y[i]-y[ch[Top-1]])*(s[ch[Top]]-s[ch[Top-1]])>=(y[ch[Top]]-y[ch[Top-1]])*(s[i]-s[ch[Top-1]]))Top--;
37         ch[++Top]=i;
38     }
39     printf("%lld",f[n]);
40     return 0;
41 }