P3628 [APIO2010]特别行动队
斯德哥尔摩
2018-08-04 11:32:34
[P3628 [APIO2010]特别行动队](https://www.luogu.org/problemnew/show/P3628)
本蒟蒻的第二道斜率优化的$DP$。
首先还是写出一个$O(n^2)$的$DP$：（但是我太菜了连这个都不会。。。）
```cpp
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])}$$
然后就可以直接搞了。
附代码：
```cpp
#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;
}
```