[BZOJ3675/Luogu3648][Apio2014]序列分割(动态规划,斜率优化)

发布于 2018-02-01  99 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3675/Luogu3648][Apio2014]序列分割(动态规划,斜率优化)

Description

小H最近迷上了一个分隔序列的游戏。在这个游戏里,小H需要将一个长度为n的非负整数序列分割成k+1个非空的子序列。为了得到k+1个子序列,小H需要重复k次以下的步骤:
1.小H首先选择一个长度超过1的序列(一开始小H只有一个长度为n的序列——也就是一开始得到的整个序列);
2.选择一个位置,并通过这个位置将这个序列分割成连续的两个非空的新序列。
每次进行上述步骤之后,小H将会得到一定的分数。这个分数为两个新序列中元素和的乘积。小H希望选择一种最佳的分割方式,使得k轮之后,小H的总得分最大。

Http

BZOJ
Luogu

Tag

动态规划,斜率优化,单调队列

解决思路

首先需要知道的是,如果分割的位置是一定的,那么最后的和也是一定的。
比如说\(ab|cd|e\),先分割前面和先分割后面是一样的,推广一下,分割成\(K\)个块的答案就是把每一个块求和再两两乘起来求和。
那么考虑\(DP\),设\(F[i][k]\)表示前\(i\)个数分割\(k\)次最大的得分,那么枚举一个小于\(i\)的\(j\)就有
\[F[i][k]=max(F[j][k]+Sum[j]*(Sum[i]-Sum[j])\]
其中\(Sum[i]\)是前\(i\)个数的前缀和。
这样的复杂度是\(O(n^2k)\)的。考虑斜率优化消去一维。
设\(j_1 < j_2\),并且\(j_2\)的答案更优,那么有
\[F[j_1][k-1]+Sum[j_1]*Sum[i]-Sum[j_1]^2 < F[j_2][k-1]-Sum[j_2]*Sum[i]-Sum[j_2]^2\]
\[F[j_1][k-1]-Sum[j_1]^2-F[j_2][k-1]+Sum[j_2]^2 < Sum[i]*(Sum[j_2]-Sum[j_1])\]
那么这样就可以用单调队列维护了。注意,因为数是非负整数,所以\(Sum[j_2]-Sum[j_1]\)可能是0,不能除过去。
\(Luogu\)需要输出方案,那么在转移的时候再记录一下从哪里分割转移过来即可。

代码

\(BZOJ\)

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
#define sqr(x) (((ll)x)*((ll)x))
#define Y(k,j1,j2) (F[j1][k&1]-sqr(Sum[j1])-F[j2][k&1]+sqr(Sum[j2]))
#define X(j1,j2) (Sum[j2]-Sum[j1])

const int maxN=100010;
const int maxK=210;
const int inf=2147483647;

int n,K;
ll Arr[maxN],Queue[maxN];
ll Sum[maxN];
ll F[maxN][2];

int main()
{
    scanf("%d%d",&n,&K);
    for (int i=1;i<=n;i++) scanf("%lld",&Arr[i]);
    for (int i=1;i<=n;i++) Sum[i]=Sum[i-1]+(ll)Arr[i];
    for (int j=1;j<=K;j++)
    {
        int now=j&1;
        int l=1,r=0;
        for (int i=1;i<=n;i++)
        {
            while ((l<r)&&(Y(j-1,Queue[l],Queue[l+1])<=Sum[i]*X(Queue[l],Queue[l+1]))) l++;//弹出队首
            F[i][now]=F[Queue[l]][now^1]+Sum[Queue[l]]*Sum[i]-sqr(Sum[Queue[l]]);
            while ((l<r)&&(Y(j-1,Queue[r-1],Queue[r])*X(Queue[r],i)>=Y(j-1,Queue[r],i)*X(Queue[r-1],Queue[r]))) r--;//弹出队尾
            Queue[++r]=i;
        }
    }
    printf("%lld\n",F[n][K&1]);
    return 0;
}

\(Luogu\)

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
#define sqr(x) (((ll)x)*((ll)x))
#define Y(k,j1,j2) (F[j1][k&1]-sqr(Sum[j1])-F[j2][k&1]+sqr(Sum[j2]))
#define X(j1,j2) (Sum[j2]-Sum[j1])

const int maxN=100010;
const int maxK=210;
const int inf=2147483647;

int n,K;
ll Arr[maxN],Queue[maxN];
ll Sum[maxN];
ll F[maxN][2];
int Path[maxN][maxK];//记录方案

int main()
{
    scanf("%d%d",&n,&K);
    for (int i=1;i<=n;i++) scanf("%lld",&Arr[i]);
    for (int i=1;i<=n;i++) Sum[i]=Sum[i-1]+(ll)Arr[i];
    for (int j=1;j<=K;j++)
    {
        int now=j&1;
        int l=1,r=0;
        for (int i=1;i<=n;i++)
        {
            while ((l<r)&&(Y(j-1,Queue[l],Queue[l+1])<=Sum[i]*X(Queue[l],Queue[l+1]))) l++;
            F[i][now]=F[Queue[l]][now^1]+Sum[Queue[l]]*Sum[i]-sqr(Sum[Queue[l]]);
            Path[i][j]=Queue[l];//记录一下是分割哪里转移过来的
            while ((l<r)&&(Y(j-1,Queue[r-1],Queue[r])*X(Queue[r],i)>=Y(j-1,Queue[r],i)*X(Queue[r-1],Queue[r]))) r--;
            Queue[++r]=i;
        }
    }
    printf("%lld\n",F[n][K&1]);
    int now=n;
    for (int i=K;i>=1;i--)//输出分割方案
    {
        printf("%d ",Path[now][i]);
        now=Path[now][i];
    }
    return 0;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3675/Luogu3648][Apio2014]序列分割(动态规划,斜率优化)


HNCJ OIer