dp 练习笔记

cbcyh · 2025-12-25 18:38:19 · 算法·理论

本文是我在做了一些动态规划题后写的，题目难度主要是绿，还有少数蓝，如果写的有误或是其他问题都可以跟我说。

前言

动态规划是一类常见且重要的算法，在洛谷题库中有 [动态规划 dp] 标签的题目数量约等于有 [贪心] 标签的题目数量加有 [二分] 标签的题目数量。这还是在不考虑其他动态规划标签以及同时拥有贪心、二分两种标签的题目的情况下粗略的比较。
本文并没有关于数位 dp、区间 dp、树形 dp、轮廓线 dp、状压 dp 和 dp 优化的内容，实在是抱歉，因为本文主要是围绕普通动态规划的技巧展开的，如果有需要我会尽快更这些动态规划的笔记。
在普通的动态规划题中，我们可能会发现，直接 dp 可能会有一些问题，比如：没有好的转移、会重或会漏。这时候，我们往往会有一些比较普遍的技巧来改进 dp，而本文正是来写这些技巧的，可能不全，因为本文是我总结自己做动态规划题的经验得来的技巧，如果有大佬补充可以通知我。

1.改变 dp 顺序

这个技巧可能很常见，但是我以前确实是很少向这方面想。这种技巧也并不难，选择一个合适的顺序也是比较重要的。下面我会通过几个例题来具体解释这个技巧。

例题 1：P14360 [CSP-J 2025] 多边形

~这题虽然是黄题，但是拿来当例题应该也没事吧~
在这个题中，一些木棍可以围成多边形的条件可以改为：木棍长度最大值小于其他值的和。那么我们就可以枚举哪根木根是最长的，但是我们会发现，直接这样 dp 是难做的。
那应该怎么改进？既然我们枚举了最长的木棍，那么其他木棍长度肯定都小于等于这根木根的长度，我们便可以改变 dp 的顺序，按木棍长度从小到大的顺序来 dp，这样我们便可以设计出状态。
状态：f_{i,j} 表示考虑了前 i 根木棍，长度之和为 j 的方案数。
转移就是一个普普通通的背包，时间复杂度也非常好分析，这里就不在一一赘述，直接上代码。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define unll unsigned long long
#define bint __int128
#define set_q priority_queue
#define unmp unordered_map
#define AK return
mt19937_64 mrand((unll) std::chrono::steady_clock::now().time_since_epoch().count());

inline int in () {
    unsigned x = 0; bool f = false; char ch = getchar();
    while (ch < '0' || ch > '9') {f |= ch == '-'; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return f ? -(int)x : x;
}

inline ll inll () {
    unll x = 0; bool f = false; char ch = getchar();
    while (ch < '0' || ch > '9') {f |= ch == '-'; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return f ? -(ll)x : x;
}

const ll p = 998244353, inf = 1ll << 59ll, infless = -(1ll << 59ll);

inline ll quickpow (ll a, ll n) {
    ll res = 1ll;
    for (; n; n >>= 1) {
        if (n & 1) {
            res *= a;
            res %= p;
        }
        a *= a;
        a %= p;
    }
    return res;
}

const int N = 5010, M = 5010;

int test, n, a[N];
ll f[N], ans, res;

inline void solve () {
    ans = 0ll;
    n = in();
    for (int i = 1; i <= n; i++) {
        a[i] = in();
    }
    sort(a + 1, a + n + 1);
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        res = 0;
        for (int j = 0; j <= a[i]; j++) {
            res += f[j];
            res %= p;
        }
        ans += (quickpow(2, i - 1) - res + p) % p;
        //printf("%d %lld\n", i, res);
        ans %= p;
        for (int j = 5000; j >= a[i]; j--) {
            f[j] += f[j - a[i]];
            f[j] %= p;
        }
    }

    printf("%lld\n", ans);
    AK;
}

int main() {
    solve();
}

例题 2：CF2161D Locked Out

上一个例题是黄题，这次直接上一个蓝题。这个题也有不用 dp 的做法，但我只记一下 dp 的做法。
先奉上我的题解，结合下文食用。
在这个题中，先正难则反，求最少需要删除多少个元素可以先求最多能保留几个元素。然后就可以考虑 dp 了。
一样的，我们发现直接 dp 好像没法转移，因为选一个数会有后效性。那么我们尝试换一个顺序来做这个题。
首先，要满足题目中说的要求，那么对于原数组第 i 个位置，[i+1,n] 这段区间中任意整数 j 的需要保证 a_j \neq a_i+1，而 [1,i-1] 这段区间中的任意整数 j 需要保证 a_j \neq a_i-1。如果我们按 a_i 从小到大的顺序来填，那么问题是不是就变简单了？
按值升顺的话，[i+1,n] 这段区间上的数就没有限制了，只剩下了 [1,i-1] 这段区间还有限制，这样就可以dp了。
状态：f_i 表示考虑了排好序后的前 i 个数，最多能保留几个数。
转移：f_i \leftarrow \max\left(1, \max_{\substack{1 \le j < i \\ (b_j \neq b_i - 1 \lor c_i < c_j)}} (f_j + 1)\right)。
时间复杂度：直接做是 \mathcal{O(n^2)} 的，结合我写的题解中的优化方法可以做到 \mathcal{O(n \log {n})}。
下面仍旧是代码部分。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define unll unsigned long long
#define bint __int128
#define set_q priority_queue
#define unmp unordered_map
#define ldouble long double
mt19937_64 mrand((unll) std::chrono::steady_clock::now().time_since_epoch().count());

inline int in() {
    unsigned int x = 0ll; bool f = false; char ch = getchar();
    while (ch < '0' || ch > '9') {f |= ch == '-'; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return f ? -(int)x : x;
}

inline ll inll() {
    unll x = 0ll; bool f = false; char ch = getchar();
    while (ch < '0' || ch > '9') {f |= ch == '-'; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return f ? -(ll)x : x;
}

const ll inf = 1ll << 59ll;
const ll infless = -inf;

const int N = 300100;

int test, n, s[N], f[N];
array<int, 2> a[N];
ll ans = 0ll, res = 0ll;

inline int lowbit (const int &x) {
    return x & (-x);
}

inline int query (const int &x) {
    int sum = 0;
    for (int y = x; y; y -= lowbit(y)) {
        sum = max(sum, s[y]);
    }
    return sum;
}

inline void modify (const int &x, const int &d) {
    for (int y = x; y <= n; y += lowbit(y)) {
        s[y] = max(s[y], d);
    }
}

inline void solve () {
    ans = 0ll;
    n = in();
    for (int i = 1; i <= n; i++) {
        a[i] = {in(), n + 1 - i};
        f[i] = s[i] = 0;
    }
    sort(a + 1, a + n + 1);
    int j = 0;
    res = 0ll;
    for (int i = 1; i <= n; i++) {
        while (j + 1 < i && a[j + 1][0] + 1 < a[i][0]) {
            j++;
            res = max(res, 1ll * f[j]);
        }
        f[i] = 1 + max((int)res, query(a[i][1]));
        modify(a[i][1], f[i]);
        ans = max(ans, 1ll * f[i]);
        //printf("x%d %d %d\n", i, j, f[i]);
    }
    printf("%lld\n", n - ans);
    return;
}

int main() {
    for (test = in(); test--; solve());
    return 0;
}

例题 3：QOJ-4807

这个题可真是纯粹的改变 dp 顺序了。~有一说一QOJ可真卡空间~
这个题我第一次做的时候花了 3 小时在想直接 dp，我根本没想到改变dp的顺序。现在来看，这个题就没那么难了。
我们不去生成原数组，而是去生成原数组的前缀和数组。记为 s，如果 s_i=s_j \pmod{k}(0 \le j < i \le n)，那么区间 [j+1,i] 就能贡献一个优秀程度。当然，s_0=0。按这种思路想下去似乎就可以 dp 了。
不难想到，直接做的顺序是按下标从小到大。我第一次做就是按着这种思路做了下去，根本没想出做法。然而当我们把顺序改为按值从小到大，这个题瞬间就明朗了。
状态：f_{i,j,l} 表示的是考虑了 [1,i] 这些数，已经填了 j 个位置，优秀程度为 l 的方案数。注意是按数字考虑，并不是下标。
直接一个暴力的转移：f_{i,j,l} \times {\binom{n-j}{q}}\rightarrow f_{i+1,j+q,l+\frac{(q - 1) \times q}{2}}。
可以发现，在这个题中，我的做法转移不是被动更新(填表法)，而是主动更新(刷表法)。因为在本题中，被动更新的话，转移代码会比较难写。
时间复杂度：\mathcal{O(nm^2k)}。下面献上代码和 AC link。

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O2", "Ofast", "inline")
#pragma GCC optimize("O3,unroll-loops")
#define ll long long
#define unll unsigned long long
#define bint __int128
#define set_q priority_queue
#define unmp unordered_map
#define ldouble long double
mt19937_64 mrand((unll) std::chrono::steady_clock::now().time_since_epoch().count());

inline int in() {
    unsigned int x = 0ll; bool f = false; char ch = getchar();
    while (ch < '0' || ch > '9') {f |= ch == '-'; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return f ? -(int)x : x;
}

inline ll inll() {
    unll x = 0ll; bool f = false; char ch = getchar();
    while (ch < '0' || ch > '9') {f |= ch == '-'; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return f ? -(ll)x : x;
}

const int TREESZ = 500100;
const ll p = 998244353, inf = 1ll << 59ll;
const ll infless = -inf;

inline ll quickpow (ll a, ll n) {
    ll res = 1ll;
    for (; n; n >>= 1) {
        if (n & 1) {
            res *= a;
            res %= p;
        }
        a *= a;
        a %= p;
    }
    return res;
}

const int N = 100;

int test, n, k, m;
ll ans = 0ll;
int f[N][N][N * N], c[N][N];

inline void solve () {
    ans = 0ll;
    n = in(), k = in(), m = in();
    for (int i = 0; (i + 1) * i / 2 <= m && i <= n; i++) {
        f[0][i][(i + 1) * i / 2] = c[n][i];
    }
    for (int i = 0; i + 1 < k; i++) {
        for (int j = 0; j <= n; j++) {
            for (int l = 0; l <= m; l++) {
                if (f[i][j][l]) {
                    for (int q = 0; q + j <= n && l + (q - 1) * q / 2 <= m; q++) {
                        f[i + 1][j + q][l + (q - 1) * q / 2] += 1ll * f[i][j][l] * c[n - j][q] % p;
                        f[i + 1][j + q][l + (q - 1) * q / 2] %= p;
                    }
                }
            }
        }
    }
    printf("%d\n", f[k - 1][n][m]);
    return;
}

int main() {
    c[0][0] = 1;
    for (int i = 1; i <= 80; i++) {
        c[i][0] = c[i][i] = 1ll;
        for (int j = 1; j < i; j++) {
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
            c[i][j] %= p;
        }
    }
    for (test = 1; test--; solve());
    return 0;
}

时间不多了，先放这 3 个。

2.辅助 dp

其实我不太清楚这个技巧专业的名字叫什么，但感觉这么说很通俗易懂，就给他起了这么个名字。
有时候我们会发现直接上 dp 会有些情况很难转移，那么我们可以考虑辅助 dp。辅助 dp 的意思是同一次 dp 中不止一个信息在动态规划，还有另一个信息也在动态规划。具体可以看例题。

例题 1：P10027 梦境世界

还是先奉上我写的题解。
做法题解里都有，这里只说思路，数组名都沿用题解里的。
如果我们直接 dp，那么很容易想到的状态是题解中的 w_{i,j}。但是我们发现我们无法转移，因为这个状态有 4 个位置可以对 w_{i,j} 产生贡献，且无法安排一个合理的顺序。
在一个点，我们只可能有 3 中操作：

• 从左边或上边走过来。
• 从这个点出发，去绕圈，也就是走出去，再喝药水回来。要注意，在一个点，我们可以绕很多圈。
• 走到右边或下边，注意，这次出去就不会再回来了。

可以看到，在转移时，我们需要考虑前 2 种操作。而这 2 种操作是独立的，那么我们可以分开算。
只考虑在一个点绕圈，直接进行 dp 似乎也很难办，那么我们可以辅助 dp。如果我们花 j 的药水绕圈，我们可以枚举一个 l，先花 l 的代价绕一圈，再花 j-l 的代价任意绕。这样，我们就能设计出状态和转移，具体见题解。
绕完了圈，我们可以再想怎么把前 2 种操作结合起来，这样我们就可以计算出 w_{i,j}。可以发现，我们肯定是从左边或上边走过来，再绕圈，那么我们再设计一个状态，用来记到当前点且没有在当前点绕圈的方案数。那么转移就比较简单了。具体见题解。
仍然是熟悉的代码环节。

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

inline int in() {
    unsigned int x = 0ll; bool f = false; char ch = getchar();
    while (ch < '0' || ch > '9') {f |= ch == '-'; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return f ? -(int)x : x;
}

const int N = 110;

int test, n, m, k, s;
bool b[N][N];
ll ans = 0ll, p, f[N][N][N], v[N][N][N], g[N][N][N], w[N][N][N];

inline void solve () {
    n = in(), m = in(), k = in(), p = in(), s = in();
    for (int i = 1; i <= s; i++) {
        int x = in(), y = in();
        b[x][y] = true;
    }
    for (int i = n; i; i--) {
        for (int j = m; j; j--) {
            if (b[i][j]) {
                continue;
            }
            g[i][j][0] = 1ll;
            for (int c = 1; c <= k; c++) {
                if (i < n) {
                    v[i][j][c] += g[i + 1][j][c - 1];
                    v[i][j][c] %= p;
                }
                if (j < m) {
                    v[i][j][c] += g[i][j + 1][c - 1];
                    v[i][j][c] %= p;
                }
            }
            for (int c = 1; c <= k; c++) {
                for (int l = 1; l <= c; l++) {
                    g[i][j][c] += g[i][j][c - l] * v[i][j][l] % p;
                    g[i][j][c] %= p;
                }
            }
        }
    }
    for (int i = 0; i <= k; i++) {
        w[1][1][i] = g[1][1][i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (b[i][j]) {
                continue;
            }
            if (i == 1 && j == 1) {
                continue;
            }
            for (int c = 0; c <= k; c++) {
                if (i > 1) {
                    f[i][j][c] += w[i - 1][j][c];
                    f[i][j][c] %= p;
                }
                if (j > 1) {
                    f[i][j][c] += w[i][j - 1][c];
                    f[i][j][c] %= p;
                }
            }
            for (int c = 0; c <= k; c++) {
                for (int l = 0; l <= c; l++) {
                    w[i][j][c] += g[i][j][c - l] * f[i][j][l] % p;
                    w[i][j][c] %= p;
                }
            }
        }
    }
    for (int i = 0; i <= k; i++) {
        ans += w[n][m][i];
        ans %= p;
    }
    printf("%lld\n", ans);
    return;
}

int main() {
    solve();
    return 0;
}

例题 2：P5615 [MtOI2019] 时间跳跃

这个题目可以看出是求出所有方案的边数和，再除以 2^n。由于输入只有一个数而且范围不大，那么……是不是可以……打表？
先放一个引理。

对于 n 条线段，如果最长的边长度小于其他边长度和，那么它们可以构成一个凸多边形。

先定一个状态：f_i 表示 n=i 时的答案(不除以 2^n)。直接 dp 显然没有很多道理，所以我们依旧辅助 dp。定义 v_i 表示选至少 2 条边，长度和为 i 但不要求构成凸多边形的边数和，g_i 表示选至少 2 条边，长度和为 i 但不要求构成凸多边形的方案数。
转移：

• f_i \leftarrow f_{i-1}
• f_i \leftarrow v_j+g_j(j>i)
• v_j \leftarrow v_{j-i}+g_{j-i}(j>i)
• g_j \leftarrow g_{j-i}
• v_j \leftarrow 2(j>i \land j-i<i)
• g_j \leftarrow 1(j>i \land j-i<i)

后面两条的转移意思是选择一条长度为 i 的边和一条长度为 j-i 的边。其他转移应该都好理解。
那么这个题就做完了。时间复杂度 O(n^3)。虽然只能拿 80 分，但是我们可以挂机打表。我本地打了不到 2 分钟。
可能说的不是很明白，请谅解。
放打完表的代码未免有些……所以放一个 80 分的代码，打表自己处理。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define unll unsigned long long
#define bint __int128
#define set_q priority_queue
#define unmp unordered_map
mt19937_64 mrand((unll) std::chrono::steady_clock::now().time_since_epoch().count());

inline ll in () {
    ll x = 0; bool f = false; char ch = getchar();
    while (ch < '0' || ch > '9') {f |= ch == '-'; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return f ? -x : x;
}

const ll p = 1000000007, inf = 1ll << 60ll, infless = -(1ll << 60ll);

inline ll quickpow (const ll &a, const ll &n) {
    ll res = 1ll, t = a;
    for (ll y = n; y > 0; y >>= 1) {
        if (y & 1) {
            res *= t;
            res %= p;
        }
        t *= t;
        t %= p;
    }
    return res;
}

const int N = 5010, M = 25000000;

int test, n;
ll ans = 0ll, top, f[N], v[M], g[M];;

inline void solve () {
    ans = 0ll;
    //solve clear !
    n = in();
    ans = f[n] * quickpow(quickpow(2, n), p - 2) % p;
    printf("%lld\n", ans);
    return;
}

int main() {
    top = 3;
    v[3] = 2, g[3] = 1;
    for (int i = 3; i <= 300; i++) {
        f[i] = f[i - 1];
        for (int j = i + 1; j <= top; j++) {
            f[i] += (v[j] + g[j]) % p;
            f[i] %= p;
        }
        top += i;
        for (int j = top; j; j--) {
            if (j >= i) {
                v[j] += v[j - i] + g[j - i];
                g[j] += g[j - i];
                v[j] %= p, g[j] %= p;
            } else {
                v[j + i] += 2;
                g[j + i]++;
                g[j + i] %= p, v[j + i] %= p;
            }
        }
    }
    for (test = in(); test--; solve());
    return 0;
}

3.去除不优项

在 dp 时，我们可能发现时间复杂度太高，但是如果让时间复杂度主要开销降一阶就可以通过。比如 \mathcal{O(n^2)} 过不了，但是 \mathcal{O(nm)} 就能过，那么我们可以考虑将其中一个 n 降一阶，这时我们就尝试去除不优项。

例题 1：CF2174B Wishing Cards

首先，我们可以发现，最优情况下，只有在 b 的前缀最大值变大时，我们才会放卡片，不然都是浪费。
状态：f_{i,j} 表示考虑了后 i 个位置，共用了 j 张卡片时的最大的快乐值。
如果你不知道为什么要从后向前做，建议你回去看看第 1 个技巧并仔细地思考一下从前往后做的坏处。
转移：f_{i,j} \leftarrow f_{x,j-t} \times (x-i) \times t
时间复杂度 \mathcal{O(n^2k^2)}。
这个时间复杂度明显是做不了的，但是如果时间复杂度中的 n 都降阶降到和 k 同阶，那么大概是可以卡过去的。
那么我们回来看 a 数组，先说结论再说证明。

最优情况下，我们选择的子序列 a_i 的值一定是递增的。

证明：如果我们选了两个位置 x,y(1 \le x < y \le n) 且 a_x \ge a_y。那么一定有 b_x<b_y。但是如果我们把 b_y 挪到 b_x 上来呢？即 b_x=\min(a_x,b_x+b_y)，那么这样肯定是不劣的，因为加上来后新的 b_x 肯定是大于原先的 b_y 的，且这样 [x,y) 这一段区间整体的快乐值也会增加。这样，命题得证。
这样我们只需要保留一个递增的 a 序列，而 a_i\le k，因此保留的数组长度肯定小于等于 k，n 降阶到了与 k 同阶。
时间复杂度 \mathcal{O(k^4)}。这个时间感觉上还是不太靠谱的，但是使劲卡常还是可以过的，注意转移时那 4 个循环的边界，这是卡常的关键。
具体操作见代码。

#pragma GCC optimize("O2", "Ofast", "inline")
#pragma GCC optimize("O3,unroll-loops", "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define unll unsigned long long
#define bint __int128
#define set_q priority_queue
#define unmp unordered_map
mt19937_64 mrand((unll) std::chrono::steady_clock::now().time_since_epoch().count());

inline unsigned in () {
    unsigned int x = 0; char ch = getchar();
    while (ch < '0' || ch > '9') {ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x;
}

const ll p = 1000000007, inf = 1ll << 60ll, infless = -(1ll << 60ll);

const int N = 100100, M = 400;

int test, n, m, a[N], k, f[M][M], b[M][2];
ll ans = 0ll;

inline void solve () {
    ans = 0ll;
    //solve clear !
    n = in(), k = in();
    m = 0;
    for (int i = 1; i <= n; i++) {
        a[i] = in();
        if (!m || a[i] > b[m][1]) {
            m++;
            b[m][0] = i, b[m][1] = a[i];
        }
    }
    for (int i = 0; i <= m + 1; i++) {
        for (int j = 0; j <= k; j++) {
            f[i][j] = -(1e9);
        }
    }
    b[m + 1][0] = n + 1;
    b[m + 1][1] = 0;
    f[m + 1][0] = 0ll;
    for (int i = m; i; i--) {
        for (int j = 0; j <= k; j++) {
            for (int x = i + 1; x <= m + 1; x++) {
                for (int t = b[i - 1][1]; t <= j && t <= b[i][1] && (x == m + 1 || j - t > t); t++) {
                    f[i][j] = max(f[i][j], f[x][j - t] + t * (b[x][0] - b[i][0]));
                }
            }
            ans = max(ans, 1ll * f[i][j]);
        }
    }
    printf("%lld\n", ans);
    return;
}

int main() {
    for (test = in(); test--; solve());
    return 0;
}

后记

文章初稿完成于 \text{2025-12-31 19:05}。如果有问题或难以理解可以通知我。
也可能有些大佬说：你这不都是基础操作吗？用得着写这么长的一个文章吗？但是本文中的内容我以前确实不是特别会用，因此写出本文，来帮助那些和我一样的 OIer 们。
本文也算是我送给大家的元旦礼物了，希望大家能有所收获。加油！2026 年一定越来越强！