[APIO2014]序列分割
2021-04-20 02:27
题面在这里
题意
将一个长度为\(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，直接算斜率的童鞋们要注意啦
代码
#includeQ[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-1]+a[i];
t[i]=t[i-1]+a[i]*a[i];
}
for(RG int i=0;i0,0});
for(RG int i=1;ifor(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