P3628 [APIO2010]特别行动队

斯德哥尔摩 · 2018-08-04 11:32:34 · 个人记录

本蒟蒻的第二道斜率优化的DP。

首先还是写出一个O(n^2)的DP：（但是我太菜了连这个都不会。。。）

for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
dp[i]=max(dp[i],dp[j]+f(sum[i]-sum[j]));

其中f(x)=ax^2+bx+c,sum[i]是前缀和。

期望50（O(n^2)在洛谷神机上1s可过），实测40（莫名其妙WA了）。

怎么办？

斜率优化！

假设j的转移优于k，那么就有：

dp[j]+f(sum[i]-sum[j])>dp[k]+f(sum[i]-sum[k])

把f(x)=ax^2+bx+c带入，合并同类项得：

dp[j]+a\times sum[j]^2-2a\times sum[i]\times sum[j]-b\times sum[j]>dp[k]+a\times sum[k]^2-2a\times sum[i]\times sum[k]-b\times sum[k]

移项得：

2a\times sum[i](sum[j]-sum[k])<(dp[j]+a\times sum[j]^2-b\times sum[j])-(dp[k]+a\times sum[k]^2-b\times sum[k])

除过去搞一下：

sum[i]<\frac{(dp[j]+a\times sum[j]^2-b\times sum[j])-(dp[k]+a\times sum[k]^2-b\times sum[k])}{2a(sum[j]-sum[k])}

然后就可以直接搞了。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 1000010
using namespace std;
int n;
long long a,b,c;
long long sum[MAXN],dp[MAXN];
int head,tail,que[MAXN];
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
inline long long f(long long x){
    return a*x*x+b*x+c;
}
inline double slope(int x,int y){
    return (double)((((dp[y]-dp[x])*1.0/(sum[y]-sum[x])-b)*1.0/a)+(sum[x]+sum[y])*1.0);
}
void work(){
    head=1;tail=1;
    for(int i=1;i<=n;i++){
        while(head<tail&&slope(que[head],que[head+1])<=2.0*sum[i])head++;
        dp[i]=f(sum[i]-sum[que[head]])+dp[que[head]];
        while(head<tail&&slope(que[tail],i)<=slope(que[tail-1],que[tail]))tail--;
        que[++tail]=i;
    }
    printf("%lld\n",dp[n]);
}
void init(){
    n=read();a=read();b=read();c=read();
    sum[0]=0;
    for(int i=1;i<=n;i++){
        int x=read();
        sum[i]=sum[i-1]+x;
    }
}
int main(){
    init();
    work();
    return 0;
}