题目连接：
http://www.lydsy.com/JudgeOnline/problem.php?id=1911
Description
有n个数，然后你需要把这n个数分成若干段，每段的权值是a*sum*sum+b*sum+c
问你怎么切，使得权值和最大
sum表示该区间的权值和
Input
三行 n,a,b,c 然后n个数，表示每个数的权值
Output
答案
Sample Input
4
-1 10 -20
2 2 3 4
Sample Output
9
数据范围n,b,c为1e6,a为5
Hint
题意
题解：
斜率优化dp
n^2 dp很显然,dp[i] = max(dp[j]+w[i][j])
这个模式比较显然的是斜率优化dp的模式
方程，假设i>j，且i优于j，则可以化为 dp[i]-dp[j]+a*(sum[i]*sum[i]-sum[j]*sum[j])+b*(sum[j]-sum[i]) / 2*a*(sum[i]-sum[j]) <sum[i]
然后斜率优化dp跑一波就好了
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int n;
long long a,b,c;
long long x;
long long sum[maxn];
long long dp[maxn];
double slope(int i,int j)
{
double up = dp[i]-dp[j]+a*(sum[i]*sum[i]-sum[j]*sum[j])+b*(sum[j]-sum[i]);
double down = 2*a*(sum[i]-sum[j]);
return up/down;
}
int l,r,q[maxn];
int main()
{
scanf("%d",&n);
scanf("%lld%lld%lld",&a,&b,&c);
for(int i=1;i<=n;i++)
{
scanf("%lld",&x);
sum[i]=sum[i-1]+x;
}
for(int i=1;i<=n;i++)
{
while(l<r&&slope(q[l+1],q[l])<sum[i])l++;
int now = q[l];
dp[i]=dp[now]+a*(sum[i]-sum[now])*(sum[i]-sum[now])+b*(sum[i]-sum[now])+c;
while(l<r&&slope(q[r],q[r-1])>slope(i,q[r]))r--;
q[++r]=i;
}
printf("%lld\n",dp[n]);
}