BZOJ3675：[Apio2014]序列分割

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

1.小H首先选择一个长度超过1的序列（一开始小H只有一个长度为n的序列——也就是一开始得到的整个序列）；

2.选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新序列。

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

【输入】
输入第一行包含两个整数n，k（k+1≤n）。

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

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

【输入样例】
7 3
4 1 3 4 0 2 3
【输出样例】
108
【提示】
【样例说明】

在样例中，小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)。

$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$

## 这篇题解的做法是$O(nlog{10^{18}})$的，想学习常规的斜率优化做法的同学可以寻找这一篇题解:[我是"这一篇题解"](https://blog.csdn.net/ShadyPi/article/details/79939983)

在APIO2018，一位$W$姓dalao在他的精彩讲课中向我们介绍了一种神奇的二分——带权二分。

这道题便是其中的一道例题。
$\space$
带权二分是什么呢？我们来具体感受一下。

首先，容易发现这道题的答案其实和划分顺序没有关系，只和划分位置有关系。本来就可以进行$dp$了。但是有一个划分段数的限制必须用两维状态，如何将它变为一维呢？

我们先考虑，如果没有划分段数的限制，那么全部切开完一定是最优决策。

于是，为了不让它全部切开完，我们给每一次切的操作一个代价$C$。我们发现，最优决策切开的段数一定随着$C$的递增而递减，当$C=+\infty$时，没有一段会被切开。具有单调性。

单调性？二分？

$Wow!$，我们可以通过二分$C$的大小来控制段数是否为$K + 1!$

简单来说，我们二分一个$C$，判断最优决策下划分段数的最大值是否为$K + 1$，如果段数偏大我们把$C$调大，反之我们把$C$调小。

问题现在变成了求不带限制，但是每一次划分带$C$的代价的情况下，最优决策的最大划分段数是多少。

我们只要每一次去枚举当前段的划分位置就可以得到一个$O(n^2)$的$dp$方程，设$s_i$为$i$处的前缀和：
$$f_i=\max{\{ f_j + s_j(s_i-s_j) - C\}}$$

转化成斜率式，得到：
$$-f_j+s_j^2+C=s_js_i-f_i \\
\to y=s_ix-f_i$$
每一个决策等价于：
$$(s_j,-f_j+s_j^2+C)$$
要$f_i$大，那么截距小，维护右下凸包即可。又因为斜率单调递增，$x$坐标单调递增，可以用单调队列做到$O(n)$

但是注意到，我们要在答案最优的情况下最大化分的段数。

因此我们要对每一个状态记录最大划分段数，并且在有很多转移一样优的情况下选择段数最大的那个转移。这个操作可以通过单调队列前端弹出的时候特判三点共线来完成，如果三点共线把最大段数向后取max。

另外，本题及其卡精度，一开始我还以为细节wa了，结果改成long double就对了。

最终代码：

```
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 1e5 + 5;
int num[maxn], n, k;

LL dp[maxn], s[maxn];
int bnum[maxn], pre[maxn];

namespace Convex {
    const long double eps = 1e-20;
    long double qx[maxn], qy[maxn], rs[maxn];
    int id[maxn];
    int f, b;
    inline int sgn(long double x) {
        return (x > -eps) - (x < eps);
    }
    void init(long double x, long double y) {
        f = b = 1;
        qx[1] = x, qy[1] = y;
        rs[1] = 1.0/0.0;
    }
    inline long double Gslope(const int &u, const int &v) {
        return (qy[v] - qy[u]) / (qx[v] - qx[u]);
    }
    void insert(const long double &x, const long double &y, const int &i) {
        qx[0] = x, qy[0] = y;
        if(x == qx[b]) return void();
        while(b - f > 0 && sgn(Gslope(b - 1, 0) - rs[b - 1]) < 0) --b;
        rs[b] = Gslope(b, 0), qx[++b] = x, qy[b] = y;
    	id[b] = i;
    }
    inline void pop(const long double &k) {
        while(b - f > 0 && sgn(rs[f] - k) <= 0) {
        	if(sgn(rs[f] - k) == 0)
        		bnum[id[f + 1]] = max(bnum[id[f + 1]], bnum[id[f]]);
            ++f;
        }
    }
    inline int GetK(const long double &k) {
        return pop(k), id[f];
    }
}

int check(LL x) {
    using namespace Convex;
    int v;
    memset(dp, -0x7f, sizeof(dp));
    dp[0] = 0, init(0, 0);
    for(register int i = 1; i <= n; ++i) {
        v = GetK(s[i]);
        dp[i] = dp[v] + s[v] * (s[i] - s[v]) - x;
        pre[i] = v, bnum[i] = bnum[v] + 1;
        insert(s[i], s[i] * s[i] - dp[i], i);
    }
    return bnum[n];
}

LL solve(LL L, LL R) {
    while(L < R - 1) {
        LL mid = L + R >> 1;
        if(check(mid) >= k + 1) L = mid;
        else R = mid;
    }
    return L;
}

void prt(int now) {
    if(!now) return ;
    prt(pre[now]);
    printf("%d ", now);
}

int main() {
    scanf("%d%d", &n, &k);
    for(register int i = 1; i <= n; ++i) {
        scanf("%d", &num[i]);
        s[i] = s[i - 1] + num[i];
    }
    LL C = solve(0, 1e18);
    check(C);
    printf("%lld\n", dp[n] + (k + 1) * C);
    //prt(pre[n]);
    return 0;
}

```

Rockdu's Blog

导航

最近发表

大佬们的友链