3675: [Apio2014]序列分割
2021-07-12 06:05
阅读：347
【样例说明】
在样例中，小H可以通过如下3轮操作得到108分：
1．-开始小H有一个序列(4，1，3，4，0，2，3)。小H选择在第1个数之后的位置
将序列分成两部分，并得到4×(1+3+4+0+2+3)=52分。
2．这一轮开始时小H有两个序列：(4)，(1，3，4，0，2，3)。小H选择在第3个数
3)=36分。
3．这一轮开始时小H有三个序列：(4)，(1，3)，(4，0，2，3)。小H选择在第5个
数字之后的位置将第三个序列分成两部分，并得到(4+0)×(2+3)=
20分。
经过上述三轮操作，小H将会得到四个子序列：(4)，(1，3)，(4，0)，(2，3)并总共得到52+36+20=108分。
【数据规模与评分】
：数据满足2≤n≤100000,1≤k≤min(n -1，200)。
先膜一发黄学长，想了好久才想明白，f[i]的计算是倒过来的
仔细观察，可以发现分割顺序是不影响最终结果的，所以我们可以从右边开始分割（想了一个小时。。。）
f[i]=max{f[j]+(s[i]-s[j])*s[j]}
斜率优化（注意变号）：
\[\frac{f[j]-f[k]+s[k]^{2}-s[j]^{2}}{s[k]-s[j]}
需要加个滚动数组节省空间
1 #include2 #include 3 using namespace std; 4 5 #define LL long long 6 const int MAXN=100005; 7 8 int n,k; 9 int a[MAXN],q[MAXN]; 10 LL f[MAXN],g[MAXN],s[MAXN]; 11 12 double slope(int k,int j) 13 { 14 return (double)(g[j]-g[k]+s[k]*s[k]-s[j]*s[j])/(s[k]-s[j]); 15 } 16 17 void dp() 18 { 19 int l=0,r=0; 20 for(int i=1;i) 21 { 22 while(l 1]) ; 23 int t=q[l]; 24 f[i]=g[t]+(s[i]-s[t])*s[t]; 25 while(l1],q[r])>slope(q[r],i)) r--; 26 q[++r]=i; 27 } 28 for(int i=1;i) swap(f[i],g[i]); 29 } 30 31 int main() 32 { 33 scanf("%d %d",&n,&k); 34 for(int i=1;i) 35 { 36 scanf("%d",&a[i]); 37 s[i]=s[i-1]+a[i]; 38 if(a[i]==0) i--,n--; 39 } 40 for(int i=1;i) dp(); 41 printf("%lld",g[n]); 42 return 0; 43 }
评论
亲，登录后才可以留言！