SCUT - 365 - 鹏哥的数字集合 - wqs二分

https://www.luogu.org/problemnew/solution/P2365

写这篇的时候还不是很明白，看一下这个东西。

https://www.cnblogs.com/CreeperLKF/p/9045491.html

还是不懂，去问学长了，叫做wqs二分。要求恰好选m个的这种题，每个物品放一个附加权值C。

https://blog.csdn.net/chenxiaoran666/article/details/83381779

既然原来选得越多越优，那么我们可以给选择一个物品增加一个代价C（C可以拿来二分），由于总贡献增长得越来越慢，所以最后肯定会形成一个单峰函数，然后我们就可以通过DP等方式来求解出此时的最优答案以及最优答案选择的物品个数，并根据选择的物品个数来更新C的值。

是通过给分段附加一个比较大的权值，使得分段越多的不一定更优了，从而控制凸壳上的点的数量，但是这个控制的时候为什么是单调的呢？

胡大佬的标程

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int MAXN = 300010;

ll dp[MAXN], a[MAXN], n, m, cnt[MAXN], que[MAXN];

ll X(int i, int j) {

    return a[j + 1] - a[i + 1];

}

ll Y(int i, int j) {

    return (dp[j] + a[j + 1] * a[j + 1]) - (dp[i] + a[i + 1] * a[i + 1]);

}

ll DP(int i, int j) {

    return dp[j] + (a[i] - a[j + 1]) * (a[i] - a[j + 1]);

}

ll solve(ll C) {

    dp[0] = 0;

    cnt[0] = 0;

    int s = 0, t = 0;

    que[++t] = 0;

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

        while(s + 1 < t && Y(que[s + 1], que[s + 2]) < 2LL * a[i] * X(que[s + 1], que[s + 2]))

            s++;

        dp[i] = DP(i, que[s + 1]) + C;

        cnt[i] = cnt[que[s + 1]] + 1;

        while(s + 1 < t && 1LL * Y(que[t], i) * X(que[t - 1], que[t]) <= 1LL * Y(que[t - 1], que[t]) * X(que[t], i))

            t--;

        que[++t] = i;

    }

    return cnt[n];

}

int main() {

    scanf("%lld%lld", &n, &m);

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

        scanf("%lld", &a[i]);

    sort(a + 1, a + 1 + n);

    ll l = 0, r = 1e12;

    while(l < r) {

        int mid = (l + r) >> 1;

        int tmp = solve(mid);

        if(tmp <= m)

            r = mid;

        else

            l = mid + 1;

    }

    solve(r);

    printf("%lld\n", dp[n] - m * r);

}

巴特西

SCUT - 365 - 鹏哥的数字集合 - wqs二分 - 斜率优化dp

最新文章

热门文章