【BZOJ-3675】序列分割 DP + 斜率优化

2021-12-01 16:35:17

3675: [Apio2014]序列分割

Time Limit: 40 Sec Memory Limit: 128 MB
Submit: 1420 Solved: 583
[Submit][Status][Discuss]

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分。
【数据规模与评分】：

数据满足2≤n≤100000,1≤k≤min(n -1，200)。

Source

Solution

个人感觉比较神的题

首先需要发现一个性质：

割k次，只要割的是正确位置，那么答案与割的顺序无关

证明：

大体上假设某串为$abcd$，如果最后要分割成$a|b|cd$那么:

先分割成$ab|cd$当前答案为$a*cd+b*cd$，再分割成$a|b|cd$,答案为$a*b+a*cd+b*cd$

先分割成$a|bcd$当前答案为$a*bcd$，在分割成$a|b|cd$,答案为$a*bcd+b*cd$

那么两式化一化就可以发现得到的是相同的。所以,对于其余的也合适;

那么可以得出一个初步的转移:

$f[i][j]=max(f[j][k-1]+sum[j]*(sum[i]-sum[j]))$其中$f[i][j]$表示的是:前i个元素,分成k段的最大分数

那么可以进行一下斜率优化,最后化出的式子:$(dp[j'][k]-dp[i'][k]+sum[i']*sum[i']-sum[j']*sum[j'])/(sum[i']-sum[j'])<=sum[i]$

有一个额外的处理,如果$a[i]==0$那么它实际上是没有意义的,反而阻碍计算,那么可以直接扔掉

内存有点小,需要滚动数组,那么滚一下就好

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

inline int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define maxn 100010

#define maxk 201

int n,K,a[maxn],que[maxn],l,r;

long long sum[maxn],dp[maxn][];

inline double slope(int i,int j,int k)

{

    return double(dp[j][k]-dp[i][k]+sum[i]*sum[i]-sum[j]*sum[j])/double(sum[i]-sum[j]);

}

int main()

{

    n=read(),K=read();

    for (int i=; i<=n; i++)

        {

            a[i]=read();

            if (a[i]==) {i--; n--; continue;}

            sum[i]=sum[i-]+a[i];

        }

    for (int j=,k=; k<=K; k++,j^=,l=r=)

        for (int tmp,i=k; i<=n; i++)

            {

                while (l<r && slope(que[l],que[l+],j^)<=sum[i]) l++;

                tmp=que[l];

                dp[i][j]=dp[tmp][j^]+(sum[i]-sum[tmp])*sum[tmp];

                while (l<r && slope(que[r-],que[r],j^)>=slope(que[r],i,j^)) r--;

                que[++r]=i;

            }

    printf("%lld\n",dp[n][K&]);

    return ;

}

WA了好几次...调了好久QAQ

码农公寓