【题目链接】
http://www.lydsy.com/JudgeOnline/problem.php?id=3675
【题意】
将n个数的序列分割k次，每次的利益为分割后两部分数值和的积，求最大利益。
【思路】
设f[i][j]表示将前i个分割j次的最大获益，则有转移式：
f[i][j]=max{ f[k][j-1]+(S(i)-S(k))*S(k) }
设a<b，若b决策优于a决策则有：
(S[b]^2-S[a]^2+f[a][j-1]-f[b][j-1])/(S[b]-S[a])<S[i]
单调队列维护下凸包，每次保持队首的最优性，维护队尾的下凸性。队列中的点至少要有一个。
【代码】
#include<set>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define trav(u,i) for(int i=front[u];i;i=e[i].nxt)
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std; typedef long long ll;
const int N = 2e5+; ll read() {
char c=getchar();
ll f=,x=;
while(!isdigit(c)) {
if(c=='-') f=-; c=getchar();
}
while(isdigit(c))
x=x*+c-'',c=getchar();
return x*f;
} int n,K,tot;
ll f[N][],cur,q[N],qh,qt,a[N],S[N];
/*
double slop(ll a,ll b) {
return (double)(S[b]*S[b]-S[a]*S[a]+f[a][cur^1]-f[b][cur^1])/(double)(S[b]-S[a]);
}
*/
ll up(ll a,ll b)
{
return (S[b]*S[b]-S[a]*S[a]+f[a][cur^]-f[b][cur^]);
}
ll down(ll a,ll b)
{
return (S[b]-S[a]);
} int main()
{
n=read(),K=read();
FOR(i,,n) {
a[++tot]=read();
if(!a[tot]) --tot;
}
n=tot;
FOR(i,,n) S[i]=S[i-]+a[i];
FOR(round,,K) {
cur^=;
qh=; qt=;
FOR(i,round,n) {
while(qh<qt&up(q[qh],q[qh+])<S[i]*down(q[qh],q[qh+])) qh++;
int t=q[qh];
f[i][cur]=f[t][cur^]+(S[i]-S[t])*S[t];
while(qh<qt&&up(q[qt-],q[qt])*down(q[qt-],i)>up(q[qt-],i)*down(q[qt-],q[qt])) qt--;
q[++qt]=i;
}
}
printf("%lld\n",f[n][cur]);
return ;
}