基于转移进行优化的 DP

从动态规划的转移入手，可以用数据结构直接优化转移过程，或者根据决策单调性使用斜率优化、四边形不等式等。

转移优化综述

过早的优化是万恶之源。

实际上最关键的事情是有一个好的状态设计，否则第一步就走错后面就完蛋了。

设计状态前，需要明确计算的是什么东西。如果状态设计的不够优秀，要考虑更换。否则，转移会变得相当困难甚至不可做。做了这么多 DP 题，读者应该有一定经验了。

当然，需要保证无后效性、满足最优子结构。

在设计好状态后，先不急着设计一个完美高效的转移。先想想最暴力的转移怎么写，然后在考虑进行优化，比如化简式子、使用数据结构、分析其单调性等。

wqs 二分

学名带权二分。常用于 2D/1D 的 DP，状态的其中一维是物品个数。这是它的明显标志，因此它比较套路。 $f_i$ 表示恰好（最多/至少）选取 $i$ 个物品时的答案，如果 $f$ 是凸函数那么则可以使用 wqs。我们可以猜测：

$O(nk)$ 过不去就是凸的。

或者也可以打表。

由于 $f$ 是凸的，因此我们可以选择二分斜率，以此计算出它的切线。有时它能直接用，有时可以对 DP 进行降维，有时和斜率优化等内容一起出现。

具体来说，我们画出所有点 $(i,f(i))$ ，假设它们构成一个上凸壳。二分斜率 $k$ ，发现随着 $k$ 的减小，直线的切点会越来越靠右。

因此二分 $k$ 直到横坐标切到我们想要的位置（比如恰好选择 $m$ 个数），那么此时的纵坐标就是答案了。

如何求出切点？我们希望这个切点的 $y$ 坐标最大，也就是在 $y$ 轴上的截距最大。设截距为 $g(x)$ ，那么切点 $(x,f(x))$ 在 $y$ 轴上的截距就是 $g(x)=f(x)-kx$ 。问题就是如何求出 $g(x)$ 的值了。

考虑 $g(x)$ 的意义，相当于钦定的 $x$ 个物品的代价都比原来少 $k$ ， $g(x)$ 相当于每个物品代价减 $k$ 之后的最优解。

$l,r$ 如何调整？要逼近 $(m,f(m))$ 如果此时切点 $(x,f(x))$ 满足 $x<m$ 时，那么应该将斜率减小，才能让切点右移。

下凸壳大致是一样的。

三点贡献可能会导致无法二分出想要的斜率。但是发现无论切到这条线上的哪个点，都不影响最终答案。采用一个优秀的二分写法可以完全避免这个问题。

概述

[国家集训队] Tree I。

给定一个无向连通图，求一棵恰好有 $k$ 条白边的最小生成树。

$n\le 5\times 10^4,m\le 10^5,w\le 100$ 。

设白边数量为 $k$ 的最小生成树是 $f(k)$ ，那么 $f$ 是一个下凸函数（其实挺显然的）。直接 wqs 即可。

查看代码

#include <bits/stdc++.h>
using namespace std; 

int n, m, need; 
struct edge {
    int u, v, w, c; 
    bool operator< (const edge &a) const {
        if (w != a.w) return w < a.w; 
        return c < a.c; 
    }
} a[100005]; 

int fa[50005], res; 
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool check(int x) {
    for (int i = 1; i <= m; ++i) if (a[i].c == 0) a[i].w -= x; 
    sort(a + 1, a + m + 1); 
    for (int i = 1; i <= n; ++i) fa[i] = i; 
    int wc = 0; res = 0; 
    for (int i = 1; i <= m; ++i) {
        int u = find(a[i].u), v = find(a[i].v); 
        if (u == v) continue; 
        fa[u] = v; res += a[i].w; wc += (a[i].c == 0); 
    }
    for (int i = 1; i <= m; ++i) if (a[i].c == 0) a[i].w += x; 
    return wc >= need; 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> m >> need; 
    for (int i = 1; i <= m; ++i) cin >> a[i].u >> a[i].v >> a[i].w >> a[i].c, ++a[i].u, ++a[i].v; 
    int L = -500, R = 500, ans; 
    while (L + 1 != R) {
        int mid = L + R >> 1; 
        if (check(mid)) ans = res + need * mid, R = mid; 
        else L = mid; 
    }
    cout << ans << "\n"; 
    return 0; 
}

数据结构优化 DP

数据结构很多，能优化 DP 的也不少。本质思想就是说，DP 的决策集合是在变化的，我们使用数据结构维护这一个集合以实现高速修改和查询。

前缀和优化

当转移方程中有区间和之类的内容，前缀和就派上用场了。

[HAOI2008] 木棍分割。

有 $n$ 根有不同长度的木棍依次连结了一起。现在允许你最多砍断 $m$ 个连接处，砍完后 $n$ 根木棍被分成了很多段，要求满足总长度最大的一段长度最小，并且输出有多少种砍的方法使得总长度最大的一段长度最小。

第一问可以二分出答案，第二问设 $f_{i,j}$ 代表将木棍分成 $i$ 段，考虑到第 $j$ 个木棍的方案数。然后可以在 $i-1$ 段的方案中找出可以段的部分将方案数加起来，前缀和优化一下即可。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int P = 10007;

int n, m; 
int a[50005], s[50005]; 
int f[50005], pre[50005], g[50005]; 

inline bool check(int x) {
    int res = 0, len = 0; 
    for (int i = 1; i <= n; ++i) {
        if (a[i] > x) return 0; 
        if (len + a[i] > x) ++res, len = a[i]; 
        else len += a[i]; 
    }
    return res <= m; 
}

int calc(int x) { // 总长度最大为 x
    int k = 0; 
    for (int i = 1; i <= n; ++i)
        for (; k < i; ++k)
            if (s[i] - s[k] <= x) { pre[i] = k; break; }
    int ans = s[n] <= x; 
    for (int i = 1; i <= n; ++i) {
        if (s[i] <= x) f[i] = 1; 
        g[i] = (g[i - 1] + f[i]) % P; 
    }
    for (int i = 2; i <= m + 1; ++i) {
        for (int j = 1; j <= n; ++j)
            f[j] = (g[j - 1] - g[pre[j] - 1] + P) % P;
        for (int j = 1; j <= n; ++j) g[j] = (g[j - 1] + f[j]) % P; 
        ans = (ans + f[n]) % P; 
    }
    return ans; 
}

int main(void) {
    scanf("%d%d", &n, &m); 
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), s[i] = s[i - 1] + a[i]; 
    int L = 0, R = s[n] + 1; 
    while (L + 1 != R) {
        int mid = L + R >> 1; 
        if (check(mid)) R = mid; 
        else L = mid; 
    }
    printf("%d %d\n", R, calc(R)); 
    return 0;
}

线段树优化

线段树很强大，可以进行区间查询，也可以对权值进行统计。这就意味着它能优化的东西很多。

[CF833B] The Bakery

Portal.

将一个长度为 $n(1\le \le 35000)$ 的序列分为 $k(1\le k\le 50)$ 段，使得总价值最大。一段区间的价值表示为区间内不同数字的个数。

设 $f(i,j)$ 代表考虑前 $i$ 个数，分为 $j$ 段的总价值。采用刷表法：

$f(i,j)$

查看代码

#include <bits/stdc++.h>
using namespace std;

struct Segment_Tree {
    int T[140005], tag[140005];
    inline void pushdown(int o) {
        if (!tag[o]) return;
        T[o << 1] += tag[o], T[o << 1 | 1] += tag[o];
        tag[o << 1] += tag[o], tag[o << 1 | 1] += tag[o];
        tag[o] = 0;
    }
    void update(int o, int l, int r, int x, int y, int k) {
        if (x <= l && r <= y) return T[o] += k, tag[o] += k, void();
        pushdown(o); int mid = l + r >> 1;
        if (x <= mid) update(o << 1, l, mid, x, y, k);
        if (mid < y) update(o << 1 | 1, mid + 1, r, x, y, k);
        T[o] = max(T[o << 1], T[o << 1 | 1]);
    }
    int query(int o, int l, int r, int x, int y) {
        if (x <= l && r <= y) return T[o];
        pushdown(o); int mid = l + r >> 1, res = 0;
        if (x <= mid) res = max(res, query(o << 1, l, mid, x, y));
        if (mid < y) res = max(res, query(o << 1 | 1, mid + 1, r, x, y));
        return res;
    }
} T[51];

int n, k, a[35005], pre[35005], lst[35005];
int f[35005][55];

int main(void) {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        pre[i] = lst[a[i]], lst[a[i]] = i;
        for (int j = 0; j < k; ++j) {
            T[j].update(1, 0, n, pre[i], i - 1, 1);
            int f = T[j].query(1, 0, n, 0, i - 1);
            T[j + 1].update(1, 0, n, i, i, f);
        }
    }
    printf("%d\n", T[k].query(1, 0, n, n, n));
    return 0;
}

整体 DP

当转移方程完全相同时，可以考虑利用线段树“整体”进行转移。

[CF115E] Linear Kingdom Races。

设 $f_i$ 为 $1\sim i$ 中获取的最大价值，有 $f_i=\max\limits_{0\le j <i} \{f_j+\operatorname{val}(j+1,i)-\operatorname{cost}(j+1,i)\}$ 。

转移式完全一样，考虑整体 DP。线段树将 $[0,i-1]$ 都减去 $a_i$ ，因为它们会修建这条道路。对于比赛来说，给 $[0,l-1]$ 加上价值，因为在这里可以得到完整的道路，也将 $f_i$ 加入线段树。那么答案就是线段树上的最大值。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 

int n, m; 
int a[200005]; i64 f[200005]; 
vector<pair<int, int>> c[200005]; 

i64 T[800005], tag[800005]; 
inline void maketag(int o, i64 k) { T[o] += k; tag[o] += k; }
inline void pushdown(int o) {
    if (!tag[o]) return; 
    maketag(o << 1, tag[o]); maketag(o << 1 | 1, tag[o]); 
    tag[o] = 0; 
}
void update(int o, int l, int r, int x, int y, i64 k) {
    if (x <= l && r <= y) return maketag(o, k); 
    pushdown(o); int mid = l + r >> 1; 
    if (x <= mid) update(o << 1, l, mid, x, y, k); 
    if (mid < y) update(o << 1 | 1, mid + 1, r, x, y, k); 
    T[o] = max(T[o << 1], T[o << 1 | 1]); 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> m; 
    for (int i = 1; i <= n; ++i) cin >> a[i]; 
    while (m--) {
        int x, y, w; cin >> x >> y >> w; 
        c[y].emplace_back(x, w); 
    }
    for (int i = 1; i <= n; ++i) {
        update(1, 0, n, 0, i - 1, -a[i]); 
        for (auto [p, v] : c[i]) update(1, 0, n, 0, p - 1, v);  
        f[i] = max(f[i - 1], T[1]); 
        update(1, 0, n, i, i, f[i]); 
    }
    return cout << f[n] << "\n", 0;
}

决策单调性

有些 DP 的转移决策是具有单调性的，这种时候就可以对决策集合进行单调性维护。单调队列可以维护决策取值范围上下界均单调变化。

wqs 二分

二分队列和栈

二分队列常用来优化有决策单调性的 DP 问题，要求对于 $i,j$ 的最优决策点 $p_i,p_j$ ，若 $i<j$ 则必有 $p_i\le p_j$ ，且能快速计算转移贡献。

工作时建立一个储存 $(j,l,r)$ 的队列，代表 $l\sim r$ 的最优决策点是 $j$ ，要保证队首的三元组满足 $l\ge i$ 。

加入决策时，如果 $i$ 比队尾的 $j$ 转移到 $l$ 更优，那么意味着队尾的三元组废了！干烂它，直到剩下最后的三元组。

取出队尾三元组，要找到一个位置 $p$ ，使得 $p$ 以前从 $j$ 转移更优， $p$ 以及以后从 $i$ 转移更优，二分即可。

[NOI2009] 诗人小 G。

完成一个需要开 long double、行末输出不能有空格的大毒瘤。

设 $f_i$ 代表考虑前 $i$ 个诗句的最小代价，有 $f_i=\min\limits_{j=0}^{i-1}\{f_j+|s_i-s_j-1-L|^P\}$ 。然后二分队列即可。

查看代码

#include <bits/stdc++.h>
using namespace std; 
typedef long double ldb; 
const ldb INF = 1e18; 

ldb poww(ldb a, int b) {
    ldb r = 1; 
    for (; b; b >>= 1, a = a * a) if (b & 1) r = r * a; 
    return r; 
}

int n, LEN, P, g[100005], s[100005];
char a[100005][35]; 
ldb f[100005]; 
ldb val(int i, int j) { return f[i] + poww(abs(s[j] - s[i] - 1 - LEN), P); }
struct Node {
    int j, l, r; 
} Q[100005]; 
int L, R; 

void print(int x) {
    if (!x) return; print(g[x]); 
    for (int i = g[x] + 1; i <= x; ++i) printf("%s%c", a[i], i == x ? '\n' : ' '); 
}

void solve(void) {
    scanf("%d%d%d", &n, &LEN, &P); 
    for (int i = 1; i <= n; ++i) {
        scanf("%s", a[i]); 
        s[i] = s[i - 1] + strlen(a[i]) + 1; 
    } Q[L = R = 1] = {0, 1, n}; 
    for (int i = 1; i <= n; ++i) {
        while (L < R && Q[L].r < i) ++L; Q[L].l = i; 
        int j = Q[L].j; g[i] = j; f[i] = val(j, i); 
        while (L < R && val(i, Q[R].l) <= val(Q[R].j, Q[R].l)) --R; 
        int LL = Q[R].l - 1, RR = Q[R].r + 2; 
        while (LL + 1 != RR) {
            int mid = LL + RR >> 1; 
            if (val(i, mid) <= val(Q[R].j, mid)) RR = mid; 
            else LL = mid; 
        }
        if (RR <= n) Q[R].r = RR - 1, Q[++R] = {i, RR, n}; 
    }
    if (f[n] > INF) puts("Too hard to arrange"); 
    else printf("%lld\n", (long long)f[n]), print(n); 
}

int main(void) {
    int T; scanf("%d", &T); 
    while (T--) solve(), puts("--------------------"); 
    return 0; 
}

基于转移进行优化的 DP

转移优化综述

wqs 二分

概述

数据结构优化 DP

前缀和优化

线段树优化

[CF833B] The Bakery

整体 DP

决策单调性

wqs 二分

二分队列和栈

四边形不等式

分治优化

斜率优化

Problemset