【算法】wqs二分/dp凸优化

wqs二分是去年省选d2t2林特卡特树捧红的。学了一发结果忘得贼tm干净QAQ,还是记一下吧。
思想挺简单的其实,我们会发现有些dp问题他们的答案随着某一维度的上升而具有单调性,然后我们选择每次dp转移的时候减少/增加一定的代价,将这个凸壳拉变形,然后看看最凸的点是在答案左侧还是右侧,之后进行调整
luoguP3620[APIO/CTSC 2007]数据备份
这个题目第一次做的时候我是用堆贪心做的,简直司 马,今天想复习下wqs,学了下发现用wqs贼简单,写了一发吊着捶我的堆贪心。
考虑一个简单的dp
dp_{i,j,0/1}表示目前考虑了前i个人,划了j条线,第i个人有没有划线的最小代价

dp_{i,j,0}=min(dp_{i-1,j,0},dp_{i-1,j,1})\\ dp_{i,j,1}=dp_{i-1,j,0}+s_i-s_{i-1}

现在发现随着j这一维度增加,dp值也在单调递增,而且增速越来越快,感性理解下的话就是开始我们会选取尽可能小的,但是小的被选光了只能选更大的了。
因此我们再设置一个函数h(x) = min(dp_{n,x,0},dp_{n,x,1})
然后二分h(x)-kx中的k,以求出最低点的x,如果x小于题目中给定条数就更新答案,把左边界向右移动,否则把右边界想左移动。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

template <typename int_qwq>

inline void re(int_qwq &x)
{
    x = 0;
    char a;
    bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b)
        x = -x;
}

const int ms = 1e5 + 10;

struct node
{
    lo x, y;

    inline bool operator < (const node &a) const
    {
        return x < a.x;
    }
}dp[ms][2];

int n, m;

lo s[ms], ans;

inline void solve(lo mid)
{
    memset(dp, 63, sizeof(dp)); dp[1][0].x = 0, dp[1][0].y = 0;
    for(ri i = 2; i <= n; i ++)
    {
        dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = (node){dp[i - 1][0].x + s[i] - s[i - 1] - mid, dp[i - 1][0].y + 1};
    }
    dp[n][0] = min(dp[n][0], dp[n][1]);
}

int main()
{
    re(n), re(m);
    lo l = 0, r = 0;
    for(ri i = 1; i <= n; i ++)
        re(s[i]), r += s[i];
    while(l <= r)
    {
        lo mid = (l + r) >> 1; solve(mid);
        if(dp[n][0].y <= m)
            ans = dp[n][0].x + mid * m, l = mid + 1;
        else
            r = mid - 1;
    }
    printf("%lld", ans);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注