\(ProblemLink\)
题意你正在玩一个关于长度为\(n\)的非负整数序列的游戏。这个游戏中你需要把序列分成 \(k+1\) 个非空的块。为了得到 \(k+1\)块，你需要重复下面的操作\(k\)次：
选择一个有超过一个元素的块（初始时你只有一块，即整个序列）
选择两个相邻元素把这个块从中间分开，得到两个非空的块。
每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。
Solution显然每一对\(i, j\), 如果它们不在同一个块中, 就会产生 \(a_i*a_j\) 的贡献.
显然有\(\Large f_{p,i}=\max({f_{p-1,j}}+s_j(s_i-s_j))\)
设转移\(j,k\),j优于k
\(j<k\)
\(\large f_{p-1,j}+(s_j*(s_i-s_j))>f_{p-1,k}+(s_k*(s_i-s_k))\)
\(\large f_{p-1,j}-s_j^2+s_is_j>f_{p-1,k}-s_k^2+s_is_k\)
\(\huge s_i>\frac{f_{p-1,k}- f_{p-1,j}+s_j^2-s_k^2}{s_j-s_k}\)
直接上斜率优化即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define IL inline #define RG register #define gi geti<int>() #define gl geti<ll>() #define gc getchar() #define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout) template<typename T>IL bool chkmax(T &x,const T &y){return x<y?x=y,1:0;} template<typename T>IL bool chkmin(T &x,const T &y){return x>y?x=y,1:0;} template<typename T> IL T geti() { RG T xi=0; RG char ch=gc; bool f=0; while(!isdigit(ch))ch=='-'?f=1:f,ch=gc; while(isdigit(ch))xi=xi*10+ch-48,ch=gc; return f?-xi:xi; } template<typename T> IL void pi(T k,char ch=0) { if(k<0)k=-k,putchar('-'); if(k>=10)pi(k/10); putchar(k%10+'0'); if(ch)putchar(ch); } const int N=1e5+7; int n,k; ll a[N],f[N][2],s[N]; int pr[N][210],now,pre; int q[N]; inline ll sqr(ll p){return p*p;} inline double slope(int j,int k) { if(s[j]==s[k])return -1e18; return (f[k][pre]-f[j][pre]+sqr(s[j])-sqr(s[k]))/static_cast<double>(s[j]-s[k]); } int main(void) { n=gi,k=gi; for(int i=1;i<=n;++i)a[i]=gi,s[i]=s[i-1]+a[i]; for(int p=1;p<=k;++p) { q[0]=0; int l=0,r=0; now=p&1,pre=now^1; for(int i=1;i<=n;++i) { while(l<r&&slope(q[l],q[l+1])<=s[i])++l; int j=q[l]; f[i][now]=f[j][pre]+(s[i]-s[j])*s[j]; pr[i][p]=j; while(l<r&&slope(q[r],i)<=slope(q[r-1],q[r]))--r; q[++r]=i; } } pi(f[n][now],'\n'); for(int i=k,w=n;i;--i)pi(w=pr[w][i],' '); return 0; }【APIO2014】Split the sequence
标签：
原文地址：https://www.cnblogs.com/LLCSBlog/p/11626960.html