首页 > 代码库 > [bzoj1911][Apio2010特别行动队]

[bzoj1911][Apio2010特别行动队]

2024-08-29 15:05:08   218人阅读

Description

技术分享

Input

技术分享

Output

技术分享

Sample Input

4-1 10 -202 2 3 4

Sample Output

9

HINT

技术分享

Solution

斜率优化动态规划

首先易得出这样的一个朴素状态转移方程

f[i]=max{f[j]+cal(sum[i]-sum[j])}

其中j<i，且cal(x)=a*x*x+b*x+c

那么设转移方程中的式子为V

若i<j，且V(j)>V(i)

那么，f[j]-f[i]+a*sum[j]^2-a*sum[i]^2+b*(sum[i]-sum[j])>2*a*(sum[j]-sum[i])*sum[i]

就可以斜率优化了

#include<cstdio>#include<cstring>#include<iostream>using namespace std;const int N=1000010;typedef long long ll;inline ll sq(ll x){  return x*x;}inline int read(){  int x=0,c=getchar(),f=1;  for(;c<48||c>57;c=getchar())    if(!(c^45))      f=-1;  for(;c>47&&c<58;c=getchar())    x=(x<<1)+(x<<3)+c-48;  return x*f;}int n,a,b,c,q[N];ll sum[N],f[N];inline double slope(int x,int y){  return (double)(f[y]-f[x]+a*(sq(sum[y])-sq(sum[x]))+b*(sum[x]-sum[y]))/(double)(2*a*(sum[y]-sum[x]));}int main(){  n=read(),a=read(),b=read(),c=read();  for(int i=1;i<=n;i++)    sum[i]=(ll)read()+sum[i-1];  int l=0,r=0;  for(int i=1;i<=n;i++){    while(l<r&&slope(q[l],q[l+1])<sum[i])l++;    int t=q[l];    f[i]=f[t]+a*sq(sum[i]-sum[t])+b*(sum[i]-sum[t])+c;    while(l<r&&slope(q[r-1],q[r])>slope(q[r],i))r--;    q[++r]=i;  }  printf("%lld\n",f[n]);  return 0;}

 

orz hzwer

[bzoj1911][Apio2010特别行动队]


联系
我们