BZOJ3675 & 洛谷3648 & UOJ104：[Apio2014]序列分割——题解

2021-04-15 05:26

阅读：434

标签：维护 printf 忽略证明 block 固定步骤 name 元素

https://www.lydsy.com/JudgeOnline/problem.php?id=3675

https://www.luogu.org/problemnew/show/P3648

http://uoj.ac/problem/104

PS：题面与题解针对于洛谷与uoj版本，bzoj请自觉把“输出做法”删去。

小H最近迷上了一个分隔序列的游戏。在这个游戏里，小H需要将一个长度为n的非负整数序列分割成k+1个非空的子序列。为了得到k+1个子序列，小H需要重复k次以下的步骤：

1.小H首先选择一个长度超过1的序列（一开始小H只有一个长度为n的序列——也就是一开始得到的整个序列）；

2.选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新序列。

每次进行上述步骤之后，小H将会得到一定的分数。这个分数为两个新序列中元素和的乘积。小H希望选择一种最佳的分割方式，使得k轮之后，小H的总得分最大。

参考：洛谷题解（虽然不算参考emmm只是斜率优化写跪了来debug用的）。

不难证出只要分割点固定那么答案固定，因此O(kn^2)不难想。

令s[i]表示前i项前缀和，那么我们有：

f[k][i]=max(f[k][i],f[k-1][j]+(s[i]-s[j])*s[j])

这个式子显然可以斜率优化，维护一个单调不增序列，令k

忽略f的前一维，则当f[k]+(s[i]-s[k])*s[k]

所以g[k,j]=(f[k]-f[j]+sqr(s[j])-sqr(s[k]))/(s[j]-s[k])

同时考虑g[k,j]>=g[j,i]时把j弹出，给出证明。

显然当g[j,i]

当g[k,j]>=g[j,i]>s[i]时k比j优仍然把j弹出。

//我还naive的想要维护单调不减序列结果各种奇葩错误emmm……

#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef double dl;
const int N=1e5+5;
const int K=205;
inline int read(){
    int X=0,w=0;char ch=0;
    while(!isdigit(ch)){w|=ch==‘-‘;ch=getchar();}
    while(isdigit(ch))X=(X3)+(X1)+(ch^48),ch=getchar();
    return w?-X:X;
}
ll f[2][N];
int n,k,nxt[N][K],q[N],s[N],l,r,now=1,pre=0;
inline ll sqr(ll k){return k*k;}
inline dl suan(int j,int k){
    if(s[j]==s[k])return -1e18;
    int i=pre;
    return (f[i][k]-f[i][j]+sqr(s[j])-sqr(s[k]))/(dl)(s[j]-s[k]);
}
int main(){
    n=read(),k=read();
    for(int i=1;i1]+read();
    for(int j=1;j){
        now^=1,pre^=1;l=r=0;
        for(int i=1;i){
            while(l1]);
            int t=q[l];
            f[now][i]=f[pre][t]+(ll)(s[i]-s[t])*s[t];nxt[i][j]=t;
            while(l1],q[r])>=suan(q[r],i))r--;
            q[++r]=i;
        }
    }
    printf("%lld\n",f[now][n]);
    int tmp=nxt[n][k];
    while(k){
        printf("%d ",tmp);
        tmp=nxt[tmp][--k];
    }
    return 0;
}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

BZOJ3675 & 洛谷3648 & UOJ104：[Apio2014]序列分割——题解

标签：维护 printf 忽略证明 block 固定步骤 name 元素

原文地址：https://www.cnblogs.com/luyouqi233/p/8893754.html

上一篇：（linux / win)怎样安装Pillow和PIL-Pillow兼容包？

下一篇：c# 24种设计模式5原型模式（Prototype）

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

亲，登录后才可以留言！

BZOJ3675 & 洛谷3648 & UOJ104：[Apio2014]序列分割——题解

评论

热门文章

推荐文章

最新文章

置顶文章

BZOJ3675 &amp; 洛谷3648 &amp; UOJ104：[Apio2014]序列分割——题解

评论

热门文章

推荐文章

最新文章

置顶文章

BZOJ3675 & 洛谷3648 & UOJ104：[Apio2014]序列分割——题解