题面在这里
题意
将一个长度为(n)的序列分成(k)段，每次分割一段长度(ge 2)的序列，
得分为两边序列元素和的乘积，求最大得分
数据范围
sol
我们发现一对元素((i,j))产生贡献(a[i]a[j])的条件是分割后元素不在同一段里
于是我们知道一对元素产生是否产生贡献分割顺序无关
那么这道题就变成了序列分段问题
设(f[i][k])表示([1,i])的序列被分为(k)段的最大贡献，(s[i]=sum_{j=1}^{i}a[j])，有
此时可以斜率优化维护上凸包，
插点((s[i],f[i][k-1]-s[i]^2))，询问(k_i=-s[i])，
由于斜率单调递减，同样是可做的
然而这里有另外一种思路
如果把长度为(n)的序列分为(n-1)段，
由上可知得分为(sum_{i=1}^{n}sum_{j=1}^{n}[i!=j]a[i]a[j])
而当一对元素((i,j))不产生贡献(a[i]a[j])时，他们在同一段里
于是我们可以求反贡献的最小值，即对于每一连续段([i,j])，
其反贡献为(sum_{k=i}^{j}sum_{l=i}^{j}[k!=l]a[k]a[l])
那么这题可能可以用区间DP做?我还是老老实实写斜率DP吧
设(f[i][k])表示([1,i])的序列被分为(k)段的最小反贡献，(t[i]=sum_{j=1}^{i}a[j]^2)，有
那么我们用普通的斜率优化插点((s[j],f[j][k-1]+frac{1}{2}(s[j]^2+t[j])))
(注意插点顺序)，询问(k_i=s[i])即可，
最后答案为(frac{1}{2}(s[n]^2-t[n])-f[n][k+1])
小细节:
(1)
该题可以先枚举(k)然后枚举(i)一层一层做，
或者维护(k+1)个凸包，然后倒着插点(!!!)
(2)
该题既可以通过维护上凸包求最大值，
也可以通过维护下凸包求最小值
(3)
注意题中(a[i]ge0)，因此(dx)有可能为0，直接算斜率的童鞋们要注意啦
代码
#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define mp make_pair
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
const dd eps=1e-10;
const int mod=1e8;
const int N=100010;
const int K=202;
il ll read(){
RG ll data=0,w=1;RG char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
return data*w;
}
il void file(){
freopen(".in","r",stdin);
freopen(".out","w",stdout);
}
struct node{ll x,y;};deque<node>Q[K];
ll n,k,a[N],s[N],t[N],f[N][K];
il void insert(ll t,node q){
while(Q[t].size()>=2&&(Q[t][Q[t].size()-1].y-Q[t][Q[t].size()-2].y)*(q.x-Q[t][Q[t].size()-1].x)>=(Q[t][Q[t].size()-1].x-Q[t][Q[t].size()-2].x)*(q.y-Q[t][Q[t].size()-1].y))
Q[t].pob();
Q[t].pub(q);
}
il ll query(ll t,ll k){
while(Q[t].size()>=2&&k*(Q[t][1].x-Q[t][0].x)>=(Q[t][1].y-Q[t][0].y))
Q[t].pof();
return Q[t].front().y-k*Q[t].front().x;
}
VI sol;
il void print(int i,int j){
if(j==1)return;
for(RG int k=i-1;~k;--k)
if(f[k][j-1]+((s[i]-s[k])*(s[i]-s[k])-(t[i]-t[k]))/2==f[i][j]){
sol.pub(k);print(k,j-1);return;
}
}
int main()
{
n=read();k=read();
for(RG int i=1;i<=n;i++){
a[i]=read();
s[i]=s[i-1]+a[i];
t[i]=t[i-1]+a[i]*a[i];
}
for(RG int i=0;i<=k;++i)insert(i,(node){0,0});
for(RG int i=1;i<=n;i++){
for(RG int j=min((ll)i,k+1);j;--j){
f[i][j]=query(j-1,s[i])+(s[i]*s[i]-t[i])/2;
insert(j,(node){s[i],f[i][j]+(s[i]*s[i]+t[i])/2});
}
}
printf("%lld
",(s[n]*s[n]-t[n])/2-f[n][k+1]);
print(n,k+1);
for(RG int i=sol.size()-1;~i;--i)
printf("%d ",sol[i]);
return 0;
}
最后鸣谢大佬yyb