洛谷 P3648 [APIO2014]序列分割 题解【斜率优化DP】

点击量：171

    要好好掌握斜率优化。

目录

Description

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

1. 小H首先选择一个长度超过1的序列（一开始小H只有一个长度为n的序列——也就是一开始得到的整个序列）；
2. 选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新序列。

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

Input

输入第一行包含两个整数n,k(k+1≤n)。

 

第二行包含n个非负整数a1,a2,…,an(0≤ai≤10^4)，表示一开始小H得到的序列。

Output

输出第一行包含一个整数，为小H可以得到的最大分数。

Sample Input

7 3
4 1 3 4 0 2 3

Sample Output

108

HINT

【样例说明】

在样例中，小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个数 字之后的位置将第二个序列分成两部分，并得到(1+3)×(4+0+2+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分。

【数据规模与评分】

第一个子任务共11分，满足1≤k<n≤10 。

第二个子任务共11分，满足1≤k<n≤50 。

第三个子任务共11分，满足1≤k<n≤200 。

第四个子任务共17分，满足2≤n≤1000,1≤k≤min{n−1,200}。

第五个子任务共21分，满足2≤n≤10000,1≤k≤min{n−1,200}。

第六个子任务共29分，满足2≤n≤100000,1≤k≤min{n−1,200}。

题解：

    这个题看上去可以区间DP，不过区间DP是$ O(n^2)$的，肯定过不了。不过我们可以发现，在序列中固定的几个位置分割，顺序不同得到的答案是相同的。

    比方说一个序列被分成了分数依次为$ x_1,x_2,x_3$的三个区间。而我们如果先分左边，再分右边，得到的答案是$ x_1\cdot (x_2+x_3)+x_2x_3=x_1x_2+x_1x_3+x_2x_3$，如果先分右边再分左边，得到的答案是$ (x_1+x_2)\cdot x_3+x_1x_2=x_1x_2+x_1x_3+x_2+x_3$，两者等价。如果我们递归地思考这个问题，无论被分成多少个区间，它们都是相等的。

    因此我们可以化区间DP为序列DP，用$ f[i][j]$表示在第i个元素后面分开第j次时的最大得分。答案是$ \max\limits_{i\in [k,n)}f[i][k]$。

    接着我们可以推出状态转移方程，

$ f[i][j]=\max\limits_{t\in[j,i)}{f[t][j-1]+(sum(n)-sum(i))(sum(i)-sum(t))}$

    $ sum(i)$代表到$ i$的前缀和，它仍然是$ O(n^2)$的。不过我们要找最大值，就要尽可能用单队优化，不过后面还有一串并不单调的式子。如果把这个方程化简，去掉max，得到

$ f[i][j]=f[t][j-1]+sum(n)sum(i)-sum(i)^2+(sum(i)-sum(n))sum(t)$，

就会发现可以用斜率优化。

    此时可以看出，我们要求的最大值为$ f[i][j]$，所以把它连同常数项设成

$ b=f[i][j]+sum(i)(sum(i)-sum(n))$

，也就是求截距的最大值，最后再转移。而可以发现此时的斜率$ k$为$ -(sum(i)-sum(n))$，而$ x=sum(t),y=f[t][j-1]$，因此

$ y=kx+b\Rightarrow f[t][j-1]=(sum(n)-sum(i))sum(t)+f[i][j]+sum(i)(sum(i)-sum(n))$。

可以发现，随着$ t$的增加，$ x$在增加，$ y$也在增加，并且当$ i$越来越大时斜率$ sum(i)-sum(n)$会越来越小。因此这是一个单增的上凸函数，像这样：

    我们的f数组一定是单调递增的，所以状态持续向右进行，每次将斜率大于$ sum(n)-sum(i)$的前面队首元素出队，接着看队尾的元素与自己是否形成了上凸，如果没有就出队，直到满足上凸。

    总的来说，题目代码量不大，不过斜率优化主要是推公式和细节。斜率优化的状态最好用$ y=kx+b$来表示，从前后出队要注意状态的表示带上q的前缀，并且注意队尾出队是与当前元素比，而不是最后三个（这个可以通过代码各部分编号输出，看哪一部分没有输出就说明可能有问题）。多个队列要注意自己的每一维下标放在哪里。

Code：

#include<cstdio>
#include<cstring>
int q[202][110000];
int l[202],r[202];
int pre[110000][202];
long long f[110000][202];
long long sum[110000];
int ans[110000];
int min(int x,int y){return x<y?x:y;}
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&sum[i]);
        sum[i]+=sum[i-1];
    }
    r[0]=1;
    for(int i=1;i<n;i++)
        for(int j=min(i,k);j;--j)
        {
            while(l[j-1]<r[j-1]-1&&f[q[j-1][l[j-1]+2]][j-1]-f[q[j-1][l[j-1]+1]][j-1]>=(sum[q[j-1][l[j-1]+2]]-sum[q[j-1][l[j-1]+1]])*(sum[n]-sum[i]))
                l[j-1]++;
            int t=q[j-1][l[j-1]+1];
            f[i][j]=f[t][j-1]+(sum[n]-sum[i])*(sum[i]-sum[t]);

            pre[i][j]=t;
            /*while(l[j]<r[j]-1&&(f[q[j][r[j]]][j]-f[q[j][r[j]-1]][j])*(sum[q[j][r[j]-1]]-sum[q[j][r[j]-2]])
                  >(f[q[j][r[j]-1]][j]-f[q[j][r[j]-2]][j])*(sum[q[j][r[j]]]-sum[q[j][r[j]-1]]))
                  r[j]--;*/
            while(l[j]<r[j]-1&&(f[i][j]-f[q[j][r[j]]][j])*(sum[q[j][r[j]]]-sum[q[j][r[j]-1]])
                  >(f[i][j]-f[q[j][r[j]-1]][j])*(sum[i]-sum[q[j][r[j]]]))
                  r[j]--;
            q[j][++r[j]]=i;
        }
    int tmp=0;
    for(int i=k;i<n;i++)
        if(f[i][k]>f[tmp][k])
            tmp=i;
    printf("%lld\n",f[tmp][k]);
    for(int i=tmp,j=k;i&&j;i=pre[i][j],j--)
        ans[j]=i;
    for(int i=1;i<=k;i++)
        printf("%d ",ans[i]);
    return 0;
}