3675: [Apio2014]序列分割

2021-07-12 06:05

阅读：348

【样例说明】

在样例中，小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 #include 2 #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(l1]);
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 }

上一篇：windows10上安装docker与碰到的坑

下一篇：各类无次数限制的免费API接口整理

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：3675: [Apio2014]序列分割
文章链接：http://soscw.com/index.php/essay/104029.html

亲，登录后才可以留言！

3675: [Apio2014]序列分割

评论

热门文章

推荐文章

最新文章

置顶文章