LG3648 [APIO2014]序列分割

2021-06-23 04:06

阅读：521

标签：name == splay const 时间复杂度操作长度 data namespace

题意

你正在玩一个关于长度为 \(n\) 的非负整数序列的游戏。这个游戏中你需要把序列分成 \(k+1\) 个非空的块。为了得到 \(k+1\) 块，你需要重复下面的操作 \(k\) 次：

选择一个有超过一个元素的块（初始时你只有一块，即整个序列）

选择两个相邻元素把这个块从中间分开，得到两个非空的块。

每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。

\(2≤n≤100000,1≤k≤\min\{n?1,200\}\)

分析

参照Tunix的题解。

首先我们根据这个分割的过程可以发现：总得分等于k+1段两两的乘积的和（乘法分配律），也就是说与分割顺序是无关的。

再对乘积进行重分组（还是乘法分配律）我们可以转化为：ans=∑第 i 段×前 i-1 段的和

所以我们就可以以分割次数为阶段进行DP啦～

令\(f[i][j]\)表示将前 \(j\) 个数分成 \(i\) 段的最大得分，那么就有
\[ f[i][j]=\max\{f[i?1][k]+s[k]×(s[j]?s[k])\} \]
这里我前些时候一直规范要求的作用就体现出来了。

令\(x>y\)，且\(x\)比\(y\)优，则
\[ f[i-1][x]-s[x]^2+s[x]s[j]>f[i-1][y]-s[y]^2+s[y]s[j] \]
这里就不能乱移项，必须保证除式中的\(\varphi(x)-\varphi(y)\)值是正的才谈得上平面中的点。必须把\(s[j]\)的系数调整成\(s[x]-s[y]\)。
\[ \frac{s[x]^2-f[i-1][x]-s[y]^2+f[i-1][y]}{s[x]-s[y]}
~~这才是正确的斜率式，跟前面的\(f[i-1][x]-s[x]^2\)是反的。~~

还是多次的斜率优化，洛谷上还要输出方案数，这也比较简单，每次转移的时候记一个\(g\)数组记录就行了。

时间复杂度\(O(kn)\)。

代码

首先是BZOJ同名题，卡空间需要滚动数组的。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define rg register
#define il inline
#define co const
templateil T read()
{
    rg T data=0;
    rg int w=1;
    rg char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        data=data*10+ch-'0';
        ch=getchar();
    }
    return data*w;
}
templateT read(T&x)
{
    return x=read();
}
using namespace std;
typedef long long ll;

co int K=201,N=1e5+1;
ll s[N];
ll f[2][N]; // edit 1: MLE

ll Up(int i,int x,int y)
{
    return s[x]*s[x]-f[i^1][x]-s[y]*s[y]+f[i^1][y];
}

ll Down(int x,int y)
{
    return s[x]-s[y];
}

ll Cal(int i,int j,int k)
{
    return f[i^1][k]+s[k]*(s[j]-s[k]);
}

int q[N];

int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
//  cerr(),k=read();
    for(int i=1;i();
    for(int i=1;i

然后是洛谷上需要输出方案，但不卡空间的。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define rg register
#define il inline
#define co const
templateil T read()
{
    rg T data=0;
    rg int w=1;
    rg char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        data=data*10+ch-'0';
        ch=getchar();
    }
    return data*w;
}
templateT read(T&x)
{
    return x=read();
}
using namespace std;
typedef long long ll;

co int K=201,N=1e5+1;
ll s[N];
ll f[K][N];
int g[K][N];

ll Up(int i,int x,int y)
{
    return s[x]*s[x]-f[i-1][x]-s[y]*s[y]+f[i-1][y];
}

ll Down(int x,int y)
{
    return s[x]-s[y];
}

ll Cal(int i,int j,int k)
{
    return f[i-1][k]+s[k]*(s[j]-s[k]);
}

int q[N];

int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
//  cerr(),k=read();
    for(int i=1;i();
    for(int i=1;isol;
    for(int i=k,j=n;i>=1;--i)
    {
        j=g[i][j];
        sol.push(j);
    }
    while(sol.size())
    {
        printf("%d ",sol.top());
        sol.pop();
    }
    return 0;
}

个人比较喜欢洛谷上的题。卡空间算一种恶心的卡常，况且写起来还那么丑。

LG3648 [APIO2014]序列分割

标签：name == splay const 时间复杂度操作长度 data namespace

原文地址：https://www.cnblogs.com/autoint/p/10200382.html

上一篇：Django表单API详解

下一篇：阿里云产品 phpwind 推送和泄露站长管理员用户ID和密码信息，曝光！曝光！曝光！

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

亲，登录后才可以留言！

LG3648 [APIO2014]序列分割

题意

分析

代码

评论

热门文章

推荐文章

最新文章

置顶文章