题面在这里 题意
将一个长度为\(n\)的序列分成\(k\)段，每次支解一段长度\(\ge 2\)的序列，
得分为两边序列元素和的乘积，求最大得分
\[2\leq n\leq100000，1\leq k\leq\min\{n-1，200\}，0≤a[i]≤10^4\]
sol我们发明一对元素\((i,j)\)孕育产生孝敬\(a[i]a[j]\)的条件是支解后元素不在同一段里
于是我们知道一对元素孕育产生是否孕育产生孝敬支解挨次无关
那么这道题就酿成了序列分段问题
设\(f[i][k]\)暗示\([1,i]\)的序列被分为\(k\)段的最大孝敬，\(s[i]=\sum_{j=1}^{i}a[j]\)，有
\[f[i][k]=max_{j=0}^{i-1}(f[j][k-1]-s[j]^2+s[i]s[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\)，有
\[f[i][k]=min_{j=0}^{i-1}[f[j][k-1]+\frac{1}{2}((s[i]-s[j])^2-(t[i]-t[j]))]\]
\[=min_{j=0}^{i-1}(f[j][k-1]+\frac{1}{2}(s[i]^2+s[j]^2-2s[i]s[j]-t[i]+t[j]))\]
\[=min_{j=0}^{i-1}(f[j][k-1]+\frac{1}{2}(s[j]^2+t[j])-s[i]s[j])+\frac{1}{2}(s[i]^2-t[i])\]
那么我们用普通的斜率优化插点\((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\n",(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