OI

NOI 复习专题 – DP

斜率优化

斜率优化其实不是很难,可以理解为在平面上的一些点作为决策点,而你现在有一条斜率为 \(k\) 的直线,你需要使其经过一个合适的点,使得这条线的截距最大/最小化。这个显然可以使这些点组成一个上/下凸包、然后二分找到斜率相近的那条线段进行转移。

一个点的两维都不连续的例题:「NOI2007」货币兑换。需要使用 CDQ 分治来做。当然,也可以强行在线使得其只能用 Splay(当然,也可以用二进制分组多一个 \(\Theta(\log)\) 艹过去)

// P4027.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;
const double eps = 1e-7;

int n, q[MAX_N], top;
double SA[MAX_N], SB[MAX_N], rate[MAX_N], f[MAX_N];

struct node
{
    double x, y;
    int id;
} nodes[MAX_N], tmp[MAX_N];

double slope(int i, int j)
{
    if (fabs(nodes[i].x - nodes[j].x) < eps)
        return 1e-15;
    return (nodes[i].y - nodes[j].y) / (nodes[i].x - nodes[j].x);
}

double calc(int i, int j)
{
    double VB = f[j] / (rate[j] * SA[j] + SB[j]);
    return SA[i] * VB * rate[j] + SB[i] * VB;
}

int binary_search(double k)
{
    int l = 1, r = top - 1, res = top;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (slope(q[mid], q[mid + 1]) <= k)
            res = mid, r = mid - 1;
        else
            l = mid + 1;
    }
    return q[res];
}

void solve(int l, int r)
{
    if (l == r)
    {
        f[l] = max(f[l], f[l - 1]), nodes[l].id = l;
        nodes[l].y = f[l] / (rate[l] * SA[l] + SB[l]);
        nodes[l].x = nodes[l].y * rate[l];
        return;
    }
    int mid = (l + r) >> 1;
    solve(l, mid), top = 0;
    for (int i = l; i <= mid; i++)
    {
        while (top > 1 && slope(q[top - 1], q[top]) <= slope(q[top - 1], i))
            top--;
        q[++top] = i;
    }
    for (int i = mid + 1; i <= r; i++)
        f[i] = max(f[i], calc(i, nodes[binary_search(-SA[i] / SB[i])].id));
    solve(mid + 1, r);
    int lptr = l, rptr = mid + 1, ptr = l;
    while (lptr <= mid && rptr <= r)
        if (nodes[lptr].x < nodes[rptr].x || (fabs(nodes[lptr].x - nodes[rptr].x) < 1e-9 && nodes[lptr].y < nodes[rptr].y))
            tmp[ptr] = nodes[lptr], lptr++, ptr++;
        else
            tmp[ptr] = nodes[rptr], rptr++, ptr++;
    while (lptr <= mid)
        tmp[ptr] = nodes[lptr], lptr++, ptr++;
    while (rptr <= r)
        tmp[ptr] = nodes[rptr], rptr++, ptr++;
    for (int i = l; i <= r; i++)
        nodes[i] = tmp[i];
}

int main()
{
    scanf("%d%lf", &n, &f[0]);
    for (int i = 1; i <= n; i++)
        scanf("%lf%lf%lf", &SA[i], &SB[i], &rate[i]), f[i] = f[0];
    solve(1, n), printf("%.10lf\n", f[n]);
    return 0;
}

决策单调性

一个很经典的例题:LibreOJ #6039. 「雅礼集训 2017 Day5」珠宝。这其中也包含了一个背包 DP 的套路。

首先这个证明很容易,对于每一个固定的价格 \(c\),转移式如下:

\[ dp[i] = \max_{j \bmod c = i \bmod c, j < i} dp[j] + pre[\frac{i – j}{c}] \]

假设要转移一个 \(j_1 < j_2 < i_1 < i_2\),显然 \(prefix\) 是一个增量单调递减的数组,如果 \(prefix\) 部分足够长,则 \(dp\) 也会足够小。这样肯定不优。

// LOJ6039.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200, MAX_K = 5e4 + 200, MAX_C = 330;

typedef long long ll;

int n, m, pos[MAX_N], ptot;
ll dp[MAX_C][MAX_K];
deque<ll> prefix[MAX_C];

void solve(int cid, int cost, int l, int r, int L, int R)
{
    if (l > r || L > R)
        return;
    int mid = (l + r) >> 1, gpt = -1;
    for (int i = L; i <= min(R, mid); i++)
        if ((mid - i <= prefix[cost].size() - 1) && (gpt == -1 || dp[cid - 1][pos[gpt]] + prefix[cost][mid - gpt] < dp[cid - 1][pos[i]] + prefix[cost][mid - i]))
            gpt = i;
    if (l == r)
        return (void)(dp[cid][pos[mid]] = dp[cid - 1][pos[gpt]] + prefix[cost][mid - gpt]);
    solve(cid, cost, l, mid, L, gpt), solve(cid, cost, mid + 1, r, gpt, R);
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, c, v; i <= n; i++)
        scanf("%d%d", &c, &v), prefix[c].push_back(v);
    for (int i = 1; i < MAX_C; i++)
        if (!prefix[i].empty())
        {
            sort(prefix[i].begin(), prefix[i].end()), reverse(prefix[i].begin(), prefix[i].end());
            for (int j = 1, siz = prefix[i].size(); j < siz; j++)
                prefix[i][j] += prefix[i][j - 1];
            prefix[i].push_front(0);
        }
    int ctot = 0;
    for (int i = 1; i < MAX_C; i++)
        if (!prefix[i].empty())
        {
            ctot++;
            for (int start_pos = 0; start_pos < i; start_pos++)
            {
                ptot = 0;
                for (int p = start_pos; p <= m; p += i)
                    pos[++ptot] = p;
                solve(ctot, i, 1, ptot, 1, ptot);
            }
        }
    for (int i = 1; i <= m; i++)
        printf("%lld ", dp[ctot][i]);
    puts("");
    return 0;
}

一些套路

无根树

例题:https://kaloronahuang.com/oi/cf-742f/

考虑先做 DP,然后再固定重心。当然需要容斥一下两个重心的情况。

还有一个和树哈希放在一起的题目:https://kaloronahuang.com/oi/bzoj-3162/

根号分治

这个老生常谈了,我记得 LOJ 有个背包题就是这么搞得。UOJ 也有个这样的题。

背包九讲 – 选讲


kal0rona

http://kaloronahuang.com

江西师大附中全机房最弱