dsy1911: [Apio2010]特别行动队
【题目描述】
有n个数，分成连续的若干段，每段的分数为a*x^2+b*x+c（a，b，c是给出的常数），其中x为该段的各个数的和。求如何分才能使得各个段的分数的总和最大。
【输入格式】
第1行:1个整数N (1 <= N <= 1000000)。
第2行：3个整数a，b，c（-5<=a<=-1,|b|<=10000000,|c|<=10000000
下来N个整数，每个数的范围为[1,100]。
【输出格式】
一个整数，各段分数总和的值最大。
【分析】
设s[i]为i的前缀和。
dp方程： f[i]=f[j]+a*(s[i]-s[j])^2+b(s[i]-s[j])+c
即 f[i]=-2a*s[i]*s[j]+a*s[j]^2-b*s[j]+f[j]+a*s[i]^2+b*s[i]+c
化成斜率优化标准形式，维护一个右上凸包即可。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define Maxn 1000010
#define LL long long LL w[Maxn],s[Maxn];
LL a,b,c; struct node
{
LL x,y;
}t[Maxn];int len=; LL f[Maxn]; bool check(int x,int y,int k)
{
LL kk=k;
return kk*(t[y].x-t[x].x)<=(t[y].y-t[x].y);
} bool check2(int x,int y,int z)
{
return (t[z].x-t[y].x)*(t[y].y-t[x].y)<=(t[y].x-t[x].x)*(t[z].y-t[y].y);
} int main()
{
int n;
scanf("%d",&n);
scanf("%lld%lld%lld",&a,&b,&c);
s[]=;
for(int i=;i<=n;i++)
{
scanf("%lld",&w[i]);
s[i]=s[i-]+w[i];
}
int st;
t[++len].x=;t[len].y=;st=;
for(int i=;i<=n;i++)
{
while(st<len&&check(st,st+,*a*s[i])) st++;
f[i]=-*a*s[i]*t[st].x+t[st].y+a*s[i]*s[i]+b*s[i]+c;
t[].x=s[i];t[].y=a*s[i]*s[i]-b*s[i]+f[i];
while(st<len&&check2(len-,len,)) len--;
t[++len]=t[];
}
printf("%lld\n",f[n]);
return ;
}
[BZOJ 1911]
2016-09-19 20:45:07