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

作者: wjyyy 分类: DP,凸包/凸壳,斜率优化DP,解析几何,解题报告,计算几何 发布时间: 2018-07-29 08:50

点击量:18

 

    要好好掌握斜率优化。

 

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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */