双指针优化dp & Luogu P1973 [NOI2011] NOI 嘉年华

题目传送门

一. 思路

首先进行离散化，将所有区间左右端点离散化，离散成 $m$ 个“离散点”，只有这些地方才可能设置为断点，不然一定是不优的。

首先考虑朴素 DP，设 $sec_{l,r}$ 为完全被包含在离散点 $l\sim r$ 内的区间总数，直接
$O(n^3)$ 暴力求就好了。

$pre_{i,j}$：离散点 $1\sim i$ 内包含的区间，一个组分到 $j$ 个区间时，另一组能分到的最大值。我们的方程应该写成这样：

$$pre_{i,j}=\max\limits_{k=1}^{k<i}\{pre_{k,j}+sec_{k,i},pre_{k,j-sec_{k,i}}\}$$

然后没有限制条件下的答案就是 $\max\limits_{j=1}^n\{\min(pre_{m,j},j)\}$

$suf_{i,j}$：离散点 $i\sim m$ 内包含的区间，一个组分到 $j$ 个区间时，另一组能分到的最大值，与 $pre$ 相似。

$d_{i,j}$：限制为离散点 $i\sim j$ 间不能有断点的情况下分到的区间较少的组别中区间数量的最大值，有状转方程：

$$d_{l,r}=\max_{x=1}^{m}\max_{y=1}^{m}\left\{\min\left(x+sec_{l,r}+y,pre_{l, x}+suf_{r, y}\right)\right\}$$

要求编号为 $i$ 的区间（左端点为 $le_i$，右端点 $ri_i$）不能被舍弃下的答案是：

$$ans_{i}=\max _{l=1}^{le_{i}} \max _{r=ri_{i}}^{m}\left\{d_{l, r}\right\}$$

可以看到，整个解题过程的瓶颈就是 $2\operatorname{D}/2\operatorname{D}$ 的求 $d_{i,j}$ 的过程，我们无法承受 $O(n^4)$ 的复杂度，要考虑优化，我们发现对于固定的 $l,r$，固定一个 $x$ 后，有一个 $y$ 使 $\min\left(x+sec_{l,r}+y,pre_{l,x}+suf_{r,y}\right)$ 最大，设这个值为 $y'_x$ ，根据 $pre_i$ 的性质，$j$ 不变时，$pre_{i,j}$ 随着 $j$ 增大而减小。

假设我们已求出了 $y'_{x}$，现在考虑 $y'_{x+a}$（$a$ 为正整数），$x+a$ 相对于 $x$，$y$ 不变，$x+sec_{l,r}+y$ 的值增加，$pre_{l,x}+suf_{r,y}$ 的值减小。$y'_x+b$ （$b$ 为正整数）相对于 $y'_x$，$x$ 不变，$x+sec_{l,r}+y$ 的值增加，$pre_{l,x}+suf_{r,y}$ 的值减小。

所以得出结论，$y'_{x+a}\le y'_x$，因为 $>y'_x$ 的决策，对 $x$ 是不优的，那么对于 $x+a$ 就更不优了。

设 $g_{l,r,x}(y)=\min\left(x+sec_{l,r}+y,pre_{l,x}+suf_{r,y}\right)$（在接下来的推导中都将 $l$ 和 $r$ 当作常量，所以简写为 $g_x(y)$），仔细想想可以发现，该函数有一个极值，即 $x+sec_{l,r}+y=pre_{l,x}+suf_{r,y}$ 时，当然因为取值都是整数他们有可能没有相等的时刻，这里指的是连成平滑曲线后的函数。并且函数 $g_x(y)$ 极点的一侧单调。

请注意现在的一个函数对应的是一个状态，横坐标对应的是决策。

于是我们尝试画出这个图象，刚才我们已经证出两条性质：

• $op$（最优决策）具有单调性。
• $g_i(j)$ 极点的一侧具有单调性。

（图像仅供参考，不代表实际上就长这样，该图象只显示出了对解题有用的特征）

• $op$（最优决策）具有单调性。
• $g_i(j)$ 极点的一侧具有单调性。

根据这两条性质，可以直接用一个指针从右往左扫，向上“爬坡”，到顶点后就记录这个值，并转到下一条函数：

转移的代码实现：

for (int i = 1; i <= cntmap; ++i) {
    for (int j = i + 1; j <= cntmap; ++j) {
        int y = n;
        for (int x = 0; x <= n; ++x) {
            while (y && min(x+sec[i][j]+y,pre[i][x]+suf[j][y])<=min(x+sec[i][j]+y-1,pre[i][x]+suf[j][y-1])) --y;
            d[i][j] = max(d[i][j], min(x + sec[i][j] + y, pre[i][x] + suf[j][y]));
        }
        ans = max(ans, d[i][j]);
    }
}

二. 细节

很重要，也很致命。

1. 向上“爬坡”时，我们需要比较指针当前位置和指针下一个位置作为决策哪一个更优，有人会用 <=，有人会用 <，如果你用 <，你会获得 ${\color{Red}0}$ 分的好成绩。问题在哪呢？如果有一个这样的函数：

   

2. 我们的代码实现和理论是有一定区别的，通常会自动忽略一些不可能是最优的决策，以本体为例，比如有这样的一个“区间”，里面刚好包含两个重合的区间（还记得加和不加引号的“区间”分别代表什么吗？）：

   

   我们当然不会舍弃这两个区间其中任意一个，因为完全可以不舍弃。但确实有一种选择是舍弃其中一个，虽然这样不优，但我们在代码中做的是将所选“区间”中区间的数量作为权值 $sec$，计算的时候加上 $sec$，就相当于忽略了舍弃一个区间这种情况，这就导致我在输出数组 $suf$ 中的值时，看到了这样的一幕：

   

可以看到，$suf$ 函数不是单调的了，这是因为我的输入数据有两个区间是重合的，我们在计算 $suf$ 时没有算只丢弃他们之中一个这种情况，对于朴素 DP 自然无伤大雅，但双指针优化 DP 要求函数有严格的单调不降性。用图像来说话就是出现了这种情况：

注意：上面这个函数表示的是数组里存的值，是用计算机算出来的值，而非实际的函数，如果函数确实就长这样他根本就满足不了双指针优化的前提条件！

因为满足 $suf_i\ge suf_{i+a}$（$a$ 为正整数），可以将这个坑填平：

填坑代码实现：

for (int i = 1; i <= cntmap; ++i) {
    for (int j = n - 1; ~j; --j) {
        pre[i][j] = max(pre[i][j], pre[i][j + 1]);
    }
}

for (int i = 1; i <= cntmap; ++i) {
    for (int j = n - 1; ~j; --j) {
        suf[i][j] = max(suf[i][j], suf[i][j + 1]);
    }
}

三. 代码

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXn = 2e2;

template <typename T> 
inline void read(T &a) {
    register char c;while (c = getchar(), c < '0' || c > '9');register T x(c - '0');while (c = getchar(), c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);}a = x;  
}
template <typename T, typename ...Argv>
inline void read(T &n, Argv &...argv) {
    read(n), read(argv...);
}

int n;
int cntmap, mapup[MAXn * 2 + 10]; map<int, int> mapdown;
int le[MAXn + 10], ri[MAXn + 10];
int sec[MAXn * 2 + 10][MAXn * 2 + 10];
int pre[MAXn * 2 + 10][MAXn + 10], suf[MAXn * 2 + 10][MAXn + 10], d[MAXn * 2 + 10][MAXn * 2 + 10], ans;
signed main() {
    read(n);
    for (int i = 1, l, len, r; i <= n; ++i) {
        read(l, len); r = l + len;
        le[i] = l;
        ri[i] = r;
        mapup[++cntmap] = l;
        mapup[++cntmap] = r;
    }
    sort(mapup + 1, mapup + 1 + cntmap);
    cntmap = unique(mapup + 1, mapup + 1 + cntmap) - (mapup + 1);
    for (int i = 1; i <= cntmap; ++i) {
        mapdown[mapup[i]] = i;
    }
    for (int i = 1; i <= n; ++i) {
        le[i] = mapdown[le[i]];
        ri[i] = mapdown[ri[i]];
    }
    for (int i = 1; i <= cntmap; ++i) {
        for (int j = i + 1; j <= cntmap; ++j) {
            for (int k = 1; k <= n; ++k) {
                if (le[k] >= i && ri[k] <= j) ++sec[i][j];
            }
        }
    }
    memset(pre, 0xc0, sizeof(pre));
    pre[1][0] = 0;
    for (int i = 2; i <= cntmap; ++i) {
        for (int j = 0; j <= n; ++j) {
            for (int k = 1; k < i; ++k) {
                pre[i][j] = max(pre[i][j], max(pre[k][j - sec[k][i]], pre[k][j] + sec[k][i]));
            }
        }
    }
    for (int i = 1; i <= cntmap; ++i) {
        for (int j = n - 1; ~j; --j) {
            pre[i][j] = max(pre[i][j], pre[i][j + 1]);
        }
    }
    memset(suf, 0xc0, sizeof(suf));
    suf[cntmap][0] = 0;
    for (int i = cntmap - 1; i; --i) {
        for (int j = 0; j <= n; ++j) {
            for (int k = cntmap; k > i; --k) {
                suf[i][j] = max(suf[i][j], max(suf[k][j - sec[i][k]], suf[k][j] + sec[i][k]));
            }
        }
    }
    for (int i = 1; i <= cntmap; ++i) {
        for (int j = n - 1; ~j; --j) {
            suf[i][j] = max(suf[i][j], suf[i][j + 1]);
        }
    }
    for (int i = 1; i <= cntmap; ++i) {
        for (int j = i + 1; j <= cntmap; ++j) {
            int y = n;
            for (int x = 0; x <= n; ++x) {
                while (y && min(x + sec[i][j] + y, pre[i][x] + suf[j][y]) <= min(x + sec[i][j] + y - 1, pre[i][x] + suf[j][y - 1])) --y;
                d[i][j] = max(d[i][j], min(x + sec[i][j] + y, pre[i][x] + suf[j][y]));
            }
            ans = max(ans, d[i][j]);
        }
    }
    printf("%d\n", ans);
    for (int i = 1; i <= n; ++i) {
        int partans = 0;
        for (int j = le[i]; j; --j) {
            for (int k = ri[i]; k <= cntmap; ++k) {
                partans = max(partans, d[j][k]);
            }
        }
        printf("%d\n", partans);
    }
}