重新学习决策单调性

前言

昨天考试T2是决策单调性, 确实看不出来…翻以前写的决策单调性的题解才略微想起来一点东西, 之前的图因为博客搬家挂掉了, 一年不到确实忘得差不多了。

问题

设函数$g(x)$的导函数单调下降且都过原点, 现有一函数$f(x)$

$$ f(x) = max\{ a_1+g(x-x_1), a_2+g(x-x_2), …, a_k+g(x-x_k) \} $$

给出函数g(x), 数列{a}, {x}和长为N的数列{p}, 对于每个$p_i$,输出$f(p_i)$。

$g(x)$的定义域为$[0, \inf)$

决策单调性

首先我们可以把图像画出来:

横向为x轴, 纵向为y轴, f(x)实际上是三个g函数最上面的那一条彩色的线。

如果我们对于每个$p_i$暴力计算对于每个$a_i, x_i$的值, 复杂度是O(kN)的, 无法接受。

考虑进行一些蛇皮操作, 根据图像不难得出一些性质:

对于$x_i, x_j$, 若$x_i < x_j$并且有一$X$使$g(X-x_i)+a_i = g(X-x_j)+a_j$, 那么有对于任意$x > X$有$g(X-x_i)+a_i < g(X-x_j)+a_j$, 对于任意$x < X$有$g(X-x_i)+a_i > g(X-x_j)+a_j$。

直观理解就只这样:

在X点处深蓝色段与浅蓝色段相交, 深蓝色段出发自比较小的xi, 浅蓝色段出发自比较大的xj, 在X之前浅蓝色段大于深蓝色段, X之后深蓝色段大于浅蓝色段。

为什么这是正确的呢? 显然xj出发的曲线增长速率在任意一点都比从xi出发的曲线大。更严谨一点就是说由于$g'(x)$单调递减, 对于定义域内任意的$x$都有$g'(x-x_i) < g'(x-x_j)$。

那问题就好办了, X点是可以二分出来的, 维护一个单调队列塞从$x_i$出发的曲线, 对队列中的每个元素$x_i$维护一个区间$(l, r)$表示如果$x$在区间$(l, r)$内, $f(x)=a_i+g(x-x_i)$。将所有的$x_i$从小到大排序, 依次尝试塞到单调队列里, 每次比较时把X二分出来, 判断X与(l, r)的关系来决定是否弹出队列尾即可。

对于下面的样例, 分别用蓝, 绿, 橙标明了x1, x2, x3的区间(l, r):

询问直接lower_bound然后计算就好了, 这就是决策单调性的套路。

例题

曾经的博客: [BZOJ 2216][Poi2011] Lightning Conductor DP

老博客的图片挂在blog搬家的时候..图片大概和上面的例子差不多。

其他类似的题目还有诗人小G等, 依稀记得有道CF四边形优化的题目可以用决策单调性水过去(多个log, QAQ)。

昨天的考试题

题目大意

Miranda有个体积可变的包包, 包包的体积最大是K, 有N个物品, 第i个物品的体积是Ci, 价值是Vi。

于是Miranda想知道她如果用体积为i的包包最大能装下多大价值的物品。

N<=10^6. K <= 50000, 1 <= Ci <= 300, 0<=Vi<=10^9

解题报告

背包? 假的背包? 真的背包? 不. 它是假的!

首先把物品按照体积分类, 每个体积的物品肯定优先选取价值大的, 于是按照价值从小到大排序, 设体积为i, 价值第j大的物品价值为w(i, j), w(i, j)第二维上的前缀和为c(i, j), 容易发现c(i, j)的离散的导函数(其实就是差分, 就等于w(i, j))单调下降。

设状态f(i, j)表示可以用体积小于等于i的物品和一个大小为j的背包得到的最大价值, 那么有递推式:

$$ f(i, j) = max\{ f(i-1, j-k\times i)+c(i, k) \} $$

设f(j)为f(i, j), g(j)为f(i-1, j), i换成s, 上面的递推式和下面的递推式等价:

$$ f(i+k\times s) = max\{ g(i)+c(k) \} $$

设函数$ r(x) = c(x\times s) $, 那么r(x)的导函数(差分)依然单调下降, 式子变成:

$$ f(i+x) = max\{ g(i)+r(x) \} | x\in {k\times s} $$

这里的g(i)可以看成常数, r(x)看成一个函数, 是不是很熟悉?

没错可以决策单调性优化!

总时间复杂度为NKlogK, CDQ写法简练快速但是我写了传统的决策单调性优化像坨**一样, 本地1.4s, 然后在OJ上愉快地被卡常…算啦懒得改了。

代码

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <climits>

#include <cstdlib>

#include <vector>

#include <ctime>

using namespace std;

typedef long long LL;

const int MAXN = 1000010;

const int MAXK = 500050;

inline int getInt () {

    int ret = 0; char ch; bool flg = false;

    while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');

    ret = ch-'0';

    while((ch = getchar()) >= '0' && ch <= '9')

        ret = ret*10+(ch-'0');

    return flg ? -ret : ret;

}

LL sum[MAXN];

int seq[MAXN], lef[MAXN], rig[MAXN];

LL mem[2][MAXK];

LL *g = mem[0], *f = mem[1];

int N, K;

inline int calcIntersection (int cur_v, int a, int b, int lst) {

	int x = a/cur_v, y = b/cur_v;

    int lb = y, rb = lst/cur_v, ans = (K*2)/cur_v;

    while(lb <= rb) {

        int mid = (lb+rb)>>1;

        LL val1 = g[a]+sum[mid-x];

        LL val2 = g[b]+sum[mid-y];

        if(val1 > val2) lb = mid+1;

        else rb = mid-1, ans = mid;

    }

    return ans*cur_v+a%cur_v;

}

inline bool compReversed (int a, int b) {return a > b;}

struct Item {

    int v, c;

} inp[MAXN];

inline bool operator < (const Item & a, const Item & b) {

    if(a.v == b.v) return a.c > b.c;

    return a.v < b.v;

}

int vmem[MAXN];

int *vclass[310], vsize[310];

int main () {

	freopen("jewelry.in", "r", stdin);

	freopen("jewelry.out", "w", stdout);

    N = getInt(), K = getInt();

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

        inp[i].v = getInt(), inp[i].c = getInt();

    sort(inp+1, inp+N+1);

    for(int i = 1; i<=N; i++) vmem[i] = inp[i].c;

    for(int i = N; i>=1; i--) {

        vclass[inp[i].v] = vmem+i;

        vsize[inp[i].v] ++;

    }

    for(int cur_v = 1; cur_v<=300; cur_v++) {

        for(int i = 1; i<=vsize[cur_v]; i++)

            sum[i] = sum[i-1]+vclass[cur_v][i-1];

        for(int p = 0; p<cur_v; p++) {

            int len = 0;

            seq[++len] = p;

            lef[len] = 1, rig[len] = K;

			int cur_pos = 1, i;

            for(int c = 1; (i=c*cur_v+p)<=K; c++) {

                while(cur_pos > len || lef[cur_pos] > i) cur_pos --;

				while(rig[cur_pos] < i) cur_pos ++;

                f[i] = max(f[i], g[seq[cur_pos]]+sum[(i-seq[cur_pos])/cur_v]);

                int ins;

                while(len) {

                    // 后者转移到ins更优

                    ins = calcIntersection(cur_v, seq[len], i, rig[len]+1);

                    if(ins > K) break;

                    else if(ins <= lef[len]) len --;

                    else {

                        rig[len] = ins-1;

                        lef[++len] = ins;

                        rig[len] = K;

                        seq[len] = i;

                        break;

                    }

                }

                if(!len) {

                    lef[++len] = 1, rig[len] = K;

                    seq[len] = i;

                }

            }

        }

        for(int i = vsize[cur_v]; i; i--) sum[i] = 0;

        swap(g, f);

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

            f[i] = max(g[i], f[i-1]);

    }

    for(int i = 1; i<K; i++) printf("%I64d ", g[i]);

    printf("%I64d\n", g[K]);

}