Lotuses's Blog

DP 技巧学习笔记

  • ~24.54K 字
  1. 1. 最优化原理
  2. 2. 无后效性
  3. 3. 动态规划设计模式

动态规划，顾名思义，就是对决策进行动态的规划。

动态规划的两个必要条件：

最优化原理

如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

如，在 dp 递推层次图的最短路时，最优解路径上每一次转移必然是最优的（在子结构中，就是在当前的状态下的最优解，和自己比不和别人比）。

当遇到题目在最优解中可以不选择最优的子结构时，就不满足最优化原理，也就不是动态规划问题了。

无后效性

即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。

即不走回头路，在上面的例子中，你选择了某一条边，之后的决策都不会影响到你选择这条边的最优解性，这就是无后效性。

在有了必要条件后，就需要设计决策与状态。

dp 的主要过程，就是 状态 – 决策 -> 状态 – 决策 -> 状态。

需要保证 dp 时间正确性的，是状态的维数和决策的复杂度。

以一道经典 dp 为例：P1854 花店橱窗布置

题目中，每一朵花只能选择一个花瓶且互不干扰，满足无后效性，且题目中的最优解为子问题之和，需要最优化原理。

因此首先可以判断可以使用 dp。

设计状态：两个思路，一是每个花瓶的状态，二是每个花的状态。

最直接使用题目的要求（花要按顺序放）的方法，对于花的状态，可以用第二维记录上一个花瓶的状态。

转移方程：。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

const int maxn = 105;
int a[maxn][maxn], f[maxn][maxn];
int pre[maxn][maxn];

std::vector<int> anslist;

int main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    
    int n, m;
    read(n, m);
    memset(a, -63, sizeof(a));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            read(a[i][j]);
        }
    }

    memset(f, -63, sizeof(f));

    int ans = -114514191, ansidi, ansidj;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int maxf = -114514191, maxid = 0;
            for (int k = 0; k < j; k++) {
                if (maxf < f[i - 1][k]) {
                    maxf = f[i - 1][k];
                    maxid = k;
                }
            }
            if (i == 1) maxf = 0;
            f[i][j] = maxf + a[i][j];
            pre[i][j] = maxid;
            
            if (i == n && ans < f[i][j]) {
                ans = f[i][j];
                ansidi = i;
                ansidj = j;
            }
        }
    }

    int i = ansidi, j = ansidj;
    while (i >= 1) {
        anslist.push_back(j);
        j = pre[i][j]; i--;
    }

    printf("%d\n", ans);
    for (int i = (int)anslist.size() - 1; i >= 0; i--) { 
        if (anslist[i] != anslist[i + 1]) {
            printf("%d ", anslist[i]);
        }
    }
    puts("");
    return 0;
}

如果将花瓶作为状态，也只需要按次序放花即可，只不过需要处理有些花瓶可以不放置花。

“这个例子具有很大的普遍性。有很多的多阶段决策问题都有着不止一种的阶段划分方法，因而往往就有不止一种的规划方法。有时各种方法所产生的效果是差不多的，但更多的时候，就像我们的例子一样，两种方法会在某个方面有些区别。

所以，在用动态规划解题的时候，可以多想一想是否有其它的解法。对于不同的解法，要注意比较，好的算法好在哪里，差一点的算法差在哪里。从各种不同算法的比较中，我们可以更深刻地领会动态规划的构思技巧。”

动态规划设计模式

动态规划的设计都有着一定的模式，一般要经历以下几个步骤。

划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的，否则问题就无法求解。

选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

**确定决策并写出状态转移方程：**之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。

**写出规划方程（包括边界条件）：**在第一部分中，我们已经给出了规划方程的通用形式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。

在某些动态规划应用中，阶段并不明显。甚至有在设计的阶段之中转移。

可以总结，状态转移一般是在相邻的两个阶段之间（有时也可以在不相邻的两个阶段间），但是尽量不要在同一个阶段内进行。

P1220 关路灯

题目大意：在区间上最大化数轴上的数 * 移动距离。（原题：最小化总和-数轴上的数 * 移动距离）

划分阶段：区间 dp 按照区间长度划分阶段

选择状态：记录区间左右端点位置，并且记录 0/1 记录结束状态（由于最大化，所以每次必然是向左向右依次点灯，这里去掉了那些不合理的移动，最终就只会停留在左端点和右端点。

状态转移方程：

1
2
3
4
5
f[i][j][0] = std::min(f[i + 1][j][0] + (pre[n] - pre[j] + pre[i]) * (ps[i + 1] - ps[i]),
f[i + 1][j][1] + (pre[n] - pre[j] + pre[i]) * (ps[j] - ps[i]));
f[i][j][1] = std::min(f[i][j - 1][0] + (pre[n] - pre[j - 1] + pre[i - 1]) * (ps[j] - ps[i]),
f[i][j - 1][1] + (pre[n] - pre[j - 1] + pre[i - 1]) * (ps[j] - ps[j - 1]));

其中 pre 为数字前缀和，ps 为数字位置。

边界：。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

int ps[101], p[101], pre[101];
int f[101][101][2];

int main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    
    memset(f, 63, sizeof(f));
    int n, c, l, r = -1;
    read(n, c);
    for (int i = 1; i <= n; i++) {
        read(ps[i], p[i]);
        pre[i] = pre[i - 1] + p[i];
    }

    f[c][c][0] = f[c][c][1] = 0;
    
    for (int len = 1; len < n; len++) {
        for (int i = 1; i <= n - len; i++) {
            int j = i + len;
            f[i][j][0] = std::min(f[i + 1][j][0] + (pre[n] - pre[j] + pre[i]) * (ps[i + 1] - ps[i]),
                                  f[i + 1][j][1] + (pre[n] - pre[j] + pre[i]) * (ps[j] - ps[i]));
            f[i][j][1] = std::min(f[i][j - 1][0] + (pre[n] - pre[j - 1] + pre[i - 1]) * (ps[j] - ps[i]),
                                  f[i][j - 1][1] + (pre[n] - pre[j - 1] + pre[i - 1]) * (ps[j] - ps[j - 1]));
            // writeln(i, j, f[i][j][0], f[i][j][1], pre[n] - pre[j - 1] + pre[i - 1]);
        }
    }
    int ans = std::min(f[1][n][0], f[1][n][1]);
    printf("%d\n", ans);
    return 0;
}

启示：不能局限于一种思维，做 dp 时要将思维打开。

例题：

P1833 樱花

多重背包，正好复习一下。

拓展背包问题的一般做法都是替换；将无限物品和有限物品替换为一个单独的物品，只是代价翻倍。

对于个数限制为 的物品，要分解为不超过 且 都要覆盖到，可以这么分解：。

分解后直接套 01 背包。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

const int maxn = 1e4 + 5;
int t[maxn], c[maxn], p[maxn];
int f[maxn << 8];
int cnt = 0;
int itv[maxn << 8], itw[maxn << 8];

void insert(int ma, int t, int c) {
    int tmp = 1;
    while (ma > tmp) {
        ++cnt;
        itv[cnt] = t * tmp;
        itw[cnt] = c * tmp;
        ma -= tmp;
        tmp <<= 1;
    }
    tmp = ma;
    if (tmp <= 0) return;
    ++cnt;
    itv[cnt] = t * tmp;
    itw[cnt] = c * tmp;
}

int main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    int bh, bm, eh, em, th, tm, n;
    read(bh, bm, eh, em, n);
    tm = - (bh * 60 + bm) + (eh * 60 + em);
    if (tm < 0) {
        writeln(0);
        return 0;
    }


    memset(f, -63, sizeof(f));

    for (int i = 1; i <= n; i++) {
        read(t[i], c[i], p[i]);
        if (t[i] == 0 && p[i] == 0) { puts("LOL YOURE A FUKING PROBLEM MAKER"); return 0; }
        if (!p[i]) p[i] = 999999;
        insert(p[i], t[i], c[i]);
        
    }

    int ans = -998244353;
    f[0] = 0;
    for (int i = 1; i <= cnt; i++) {
        for (int v = tm; v >= itv[i]; v--) {
            f[v] = std::max(f[v], f[v - itv[i]] + itw[i]);
            ans = std::max(ans, f[v]);
            // writeln(i, v, f[v]);
        }
    }
    writeln(ans);
    return 0;
}

P1725 琪露诺

经典的单调队列优化线性 dp。使用单调队列 维护滑动窗口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

const int maxn = 2e5 + 5;
int a[maxn];
int f[maxn];

std::deque<std::pair<int, int> > q;

void push(int id) {
    while (!q.empty() && q.front().first <= f[id]) q.pop_front();
    q.push_back(std::make_pair(f[id], id));
}

int query(int id) {
    while (!q.empty() && q.front().second <= id) q.pop_front();
    if (q.empty()) return -1145141919;
    return q.front().first;
}

int main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    
    memset(f, -63, sizeof(f));
    f[0] = 0;
    int n, l, r, ans = -1145141919;
    read(n, l, r);
    for (int i = 0; i <= n; i++) {
        read(a[i]);
    }
    for (int i = 1; i <= n; i++) {
        // for (int j = std::max(0, i - r); j <= i - l; j++) {
        //     f[i] = std::max(f[i], f[j] + a[i]);
        // }
        if (i - l >= 0) {
            push(i - l);
        }
        int fmax = query(std::max(0, i - r) - 1);
        f[i] = fmax + a[i];
        // writeln(i, f[i]);
        if (i > n - r) ans = std::max(ans, f[i]);
    }
    printf("%d\n", ans);
    return 0;
}

P3842 [TJOI2007] 线段

一道有意思的简单线性 dp。不难的状态推导，不刁难人。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

#define abs(a) ((a) < 0 ? -(a) : (a))

int L[20004], R[20004];
int f[20004][2];

int main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    
    int n;
    read(n);
    for (int i = 1; i <= n; i++) {
        read(L[i], R[i]);
    }

    f[1][0] = R[1] - 1 + R[1] - L[1];
    f[1][1] = R[1] - 1;

    for (int i = 2; i <= n; i++) {
        f[i][0] = std::min(f[i - 1][0] + abs(L[i - 1] - R[i]) + R[i] - L[i],
                           f[i - 1][1] + abs(R[i - 1] - R[i]) + R[i] - L[i]);
        f[i][1] = std::min(f[i - 1][0] + abs(L[i - 1] - L[i]) + R[i] - L[i],
                           f[i - 1][1] + abs(R[i - 1] - L[i]) + R[i] - L[i]);
    }

    printf("%d\n", std::min(f[n][0] + (n - L[n]), f[n][1] + (n - R[n])) + n - 1);
    return 0;
}

P1775 石子合并（弱化版）

区间合并模板， 的应用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

const int maxn = 505;
int m[maxn], f[maxn][maxn], s[maxn];

int main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    
    memset(f, 63, sizeof(f));

    int n;
    read(n);
    for (int i = 1; i <= n; i++) {
        read(m[i]);
        s[i] = s[i - 1] + m[i];
        f[i][i] = 0;
    }
    for (int len = 1; len <= n - 1; len++) {
        for (int i = 1; i <= n - len; i++) {
            int j = i + len;
            for (int k = i; k <= j - 1; k++) {
                f[i][j] = std::min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
            }
        }
    }
    writeln(f[1][n]);
    return 0;
}

P1352 没有上司的舞会

树形 dp 基本模型。

思路：在树上递推。首先寻找根，推式子：，。

以记忆化搜索的形式书写，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

const int maxn = 12004;
int r[maxn];

struct Edge {
    int u, v;
};
std::vector<Edge> G[maxn];
int faa[maxn];
int rem[maxn][2];

int dfs(int cur, int t) {
    if (rem[cur][t] != 0) {
        return rem[cur][t];
    }
    if (G[cur].size() == 0) {
        if (t == 0) return 0;
        else return rem[cur][t] = r[cur];
    }
    int ans = 0;
    if (t == 0) {
        for (Edge e : G[cur]) {
            ans += std::max(dfs(e.v, 0), dfs(e.v, 1));
        }
    } else {
        for (Edge e : G[cur]) {
            ans += dfs(e.v, 0);
        }
        ans += r[cur];
    }
    return rem[cur][t] = ans;

}

int main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    
    int n;
    read(n);
    for (int i = 1; i <= n; i++) {
        read(r[i]);
    }

    int u, v;
    for (int i = 1; i <= n - 1; i++) {
        read(u, v);
        G[v].push_back({v, u});
        faa[u]++;
    }
    int fa;
    for (int i = 1; i <= n; i++) {
        if (!faa[i]) {
            fa = i;
            break;
        }
    }
    writeln(std::max(dfs(fa, 1), dfs(fa, 0)));
    return 0;
}

P1122 最大子树和

树上贪心？为什么会跑到 dp 题单里；

对每一个子树统计子树和，如果是负数，那么不选择这个子树是必要的。反之，是必要的。

而有可能出现剪掉上面枝条的可能，所以在路上维护子树（非负树叶枝条）的最大值，一并算到 ans 中。可以证明是维护到了所有的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

const int maxn = 20005;
int c[maxn];

struct Edge {
    int u, v;
};
std::vector<Edge> G[maxn];
void insert(int u, int v) {
    G[u].push_back({u, v});
    G[v].push_back({v, u});
}

int ans = -998244353;
int dfs(int cur, int fa = -1) {
    int cans = c[cur];
    for (Edge e : G[cur]) {
        if (e.v != fa) {
            int q = dfs(e.v, cur);
            if (q > 0) cans += q;
        }
    }
    ans = std::max(ans, cans);
    return cans;
}

int main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    int n;
    read(n);
    for (int i = 1; i <= n; i++) {
        read(c[i]);
    }
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        read(u, v);
        insert(u, v);
    }

    dfs(1);
    writeln(ans);
    return 0;
}

P2016 战略游戏

类似于没有上司的晚会，只是代价最小化和代价全为 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

const int maxn = 12004;
int r[maxn];

struct Edge {
    int u, v;
};
std::vector<Edge> G[maxn];
int rem[maxn][2];

void insert(int u, int v) {
    G[u].push_back({u, v});
    G[v].push_back({v, u});
}

int dfs(int cur, int t, int fa = -1) {
    if (rem[cur][t] != 0) {
        return rem[cur][t];
    }
    if (G[cur].size() == 0) {
        if (t == 0) return 0;
        else return rem[cur][t] = 1;
    }
    int ans = 0;
    if (t == 0) {
        for (Edge e : G[cur]) {
            if (e.v != fa)
            ans += dfs(e.v, 1, cur);
        }
    } else {
        for (Edge e : G[cur]) {
            if (e.v != fa)
            ans += std::min(dfs(e.v, 0, cur), dfs(e.v, 1, cur));
        }
        ans++;
    }
    return rem[cur][t] = ans;

}

int main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    
    int n;
    read(n);

    int u, t, v;
    for (int i = 0; i <= n - 1; i++) {
        read(u, t);
        for (int j = 1; j <= t; j++) {
            read(v);
            insert(u, v);
        }
    }
    int fa = 0;
    writeln(std::min(dfs(fa, 1), dfs(fa, 0)));
    return 0;
}

P1874 快速求和

类似于背包的线性 dp，看上去像区间 dp，但是和区间合并关系不大，且状态只和到当前节点的数值和到了哪有关，所以直接二维线性 dp。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

const int maxn = 45;
int s[maxn], n = 0;
int m[maxn][maxn];
int f[maxn][100005];

void read() {
	char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <='9') s[++n] = ch - '0', ch = getchar();
}

int main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    
    int q;
    read();
    for (int i = 1; i <= n; i++) {
        m[i][i] = s[i];
        for (int j = i + 1; j <= n; j++) {
            m[i][j] = m[i][j - 1] * 10 + s[j];
        }
    }
    read(q);
    memset(f, 63, sizeof(f));
	f[0][0] = -1;
    for (int i = 1; i <= n; i++) {
    	for (int j = 0; j < i; j++) {
    		for (int k = q; k >= m[j + 1][i]; k--) {
                f[i][k] = std::min(f[i][k], f[j][k - m[j + 1][i]] + 1);
			}
		}
	}
    if (f[n][q] == f[0][1]) puts("-1");
    else writeln(f[n][q]);
    return 0;
}

P3147【USACO16OPEN】262144

运用了一点倍增的思想（因为是合并问题）。

思维路程：因为合并而想到区间 dp。发现区间 dp 由于范围太大好像不太现实；突然发现合并的数并不大，有没有可能把数作为一维当作状态？

可以发现，对于每一个数值和一个起点，必然有唯一的一个最小的右端点使左右端点覆盖的区间可以构成这个数值（这里要求必须要用到边界，否则就不一定能相邻的合并了，一开始没想到也是因为怕没用到边界）。

那么发现左右两个相同的数值的区间好像可以合并？

写出递推式：

数值为 ，左端点为 时，通过第一次取用 寻找 的最小区间；如果可以找到，那么再次寻找从该位置开始向后一位的构成 的最小区间位置。无论寻找不寻找到，都回去更新 。

发现好像刚好能够继承左右边界都用了的条件，那么就可以 dp 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

const int maxn = 524288;
int b[maxn];
int f[60][524288];
int maxv;

int main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    
    int n;
    read(n);
    memset(f, 63, sizeof(f));
    maxv = f[0][0];
    for (int i = 1; i <= n; i++) {
        read(b[i]);
        f[b[i]][i] = i;
    }
    
    int maxx = 0;
    for (int i = 2; i <= 58; i++) {
        for (int j = 1; j <= n; j++) {
            if (f[i - 1][j] != maxv) {
                f[i][j] = std::min(f[i][j], f[i - 1][f[i - 1][j] + 1]);
            }
            if (f[i][j] != maxv) maxx = i;
        }
    }
    // writeln(f[2][2]);
    writeln(maxx);
    return 0;
}

这道题思维也算挺有意思的。

P2340【USACO03FALL】Cow Exhibition G

一个互相依赖的背包问题，要求两个权值和都要大于 0。

很正常地想到了二维，将这个两个权值都并了进去，但是好像值没什么用了；

那么将其中一个权值变成数组的权值，加入一个序号 ， 表示在第 头牛智商为 时情商的最大值 。两个值互不影响，最终算答案时只需要简单枚举筛选即可，这个设计方案非常聪明。

只是，由于 的可负性，而且范围还挺大的，挺难处理的，还需要加上 。

实现比较复杂，感觉不止黄。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

template<typename T>
void read(T &r) { r = 0; static char ch, last; ch = getchar(), last = 'z'; while (ch < '0' || ch > '9') last = ch, ch = getchar(); while (ch >= '0' && ch <= '9') r = (r << 1) + (r << 3) + (ch ^ 48), ch = getchar(); r = (last == '-') ? -r : r; }
template<typename T, typename...Ts>
void read(T &arg, Ts&...arg_left) { read(arg); read(arg_left...); }

template<typename T>
void write(T x) { if (x < 0) putchar('-'), x = -x; int len = 0; static char ch[100]; while (x) ch[++len] = x % 10 + '0', x /= 10; if (!len) ch[++len] = '0'; while (len) putchar(ch[len--]); }
template<typename T, typename...Ts>
void write(T arg, Ts...arg_left) { write(arg); putchar(' '); write(arg_left...); }
template<typename T>
void writeln(T x) { write(x); putchar('\n'); }
template<typename T, typename...Ts>
void writeln(T arg, Ts...arg_left) { write(arg); putchar(' '); write(arg_left...); putchar('\n'); }

// #define __DEBUG
#ifdef __DEBUG
#define debug(arg, args...) { printf("db <%d> ", __LINE__); writeln(arg, ##args); }
#else
#define debug(arg, args...) {}
#endif

const int maxn = 405;
int s[maxn], r[maxn];
int f[2 * maxn * 1000 + 2000];

int main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    
    memset(f, -63, sizeof(f));

    int n;
    read(n);
    for (int i = 1; i <= n; i++) {
        read(s[i], r[i]);
    }
    memset(f, -63, sizeof(f));
	f[400000] = 0;
	for(int i = 1; i <= n; i++)
	{
		if(s[i] >= 0) {
			for (int j = 800000; j >= s[i]; j--) {
				f[j] = std::max(f[j], f[j - s[i]] + r[i]);
            }
        }
		else {
			for (int j = 0; j <= 800000 + s[i]; j++) {
				f[j] = std::max(f[j], f[j - s[i]] + r[i]);
            }
        }
	}
    int ans = 0;
	for (int i = 400000; i <= 800000; i++){
		if (f[i] > 0) {
			ans = std::max(ans, i + f[i] - 400000);
        }
    }

    writeln(ans);
    return 0;
}

CF149D Coloring Brackets

染色区间 dp，大致题意是给配对的括号分别染色，符合题目要求的染色方案的总数。

括号->区间 dp；

通过中点转移的方式分割序列，确定递推顺序，使用搜索确定拓扑序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>

#define int long long

const int mod = 1000000007;
const int maxn = 705;
char s[maxn];
int n, R[maxn];
std::stack<int> st;
int f[maxn][maxn][3][3];

// R[l] != r
// f[0][1] = (f[0][1] + f[0][2]) * (f[0][1] + f[1][1] + f[2][1]) - f[0][2] *
// f[2][1] - f[0][1] * f[1][1] f[0][2] =                                         * (f[0][2] +
// f[1][2] + f[2][2])                                    2                                     2 f[1][0] = (f[1][0]
// + f[1][2]) * (f[0][0] + f[1][0] + f[2][0]) - f[1][0] * f[0][0] - f[1][2] *
// f[2][0] f[2][0] = (f[2][0] + f[2][1]) *                                                                     2
// 2    1            1    0

// R[l] == r
// f[0][1] = f[0][0] + f[0][2] + f[1][0] + f[1][2] + f[2][0] + f[2][2]
// f[0][2] =                                1                                     1                                     1
// f[1][0] = f[0][0] + f[0][1] + f[0][2] + f[2][0] + f[2][1] + f[2][2]
// f[2][0] =                                                                 1                 1                 1

void dfs(int l, int r) {
    if (R[l] < l || R[l] > r) {
        return;
    } else if (l + 1 == r) {
        f[l][r][0][0] = f[l][r][1][1] = f[l][r][1][2] = f[l][r][2][1] =
                f[l][r][2][2] = 0;
        f[l][r][0][1] = f[l][r][1][0] = f[l][r][0][2] = f[l][r][2][0] = 1;
    } else {
        if (r == R[l]) {
            dfs(l + 1, r - 1);
            auto &p = f[l + 1][r - 1];
            f[l][r][0][1] = p[0][0] + p[0][2] + p[1][0] + p[1][2] + p[2][0] + p[2][2]; f[l][r][0][1] %= mod;
            f[l][r][0][2] = p[0][0] + p[0][1] + p[1][0] + p[1][1] + p[2][0] + p[2][1]; f[l][r][0][2] %= mod;
            f[l][r][1][0] = p[0][0] + p[0][1] + p[0][2] + p[2][0] + p[2][1] + p[2][2]; f[l][r][1][0] %= mod;
            f[l][r][2][0] = p[0][0] + p[0][1] + p[0][2] + p[1][0] + p[1][1] + p[1][2]; f[l][r][2][0] %= mod;
            // for (int i = 0; i <= 2; i++){
            //         for (int j = 0; j <= 2; j++){
            //                 if (j != 1) f[l][r][0][1] += f[l+1][r-1][i][j];
            //                 if (j != 2) f[l][r][0][2] += f[l+1][r-1][i][j];
            //                 if (i != 1) f[l][r][1][0] += f[l+1][r-1][i][j];
            //                 if (i != 2) f[l][r][2][0] += f[l+1][r-1][i][j];
            //         }
            // }
        } else {
            dfs(l, R[l]);
            dfs(R[l] + 1, r);
            auto &ll = f[l][R[l]], &rr = f[R[l] + 1][r];

            for (int i = 0; i <= 2; i++) {
                for (int j = 0; j <= 2; j++) {
                    for (int p = 0; p <= 2; p++) {
                        for (int q = 0; q <= 2; q++) {
                            if ((j == 1 && p == 1) || (j == 2 && p == 2)) continue;
                            f[l][r][i][q] += (ll[i][j] * rr[p][q] % mod);
                            f[l][r][i][q] %= mod;
                        }
                    }
                }
            }
        }
    }
}

signed main() {
#ifdef LOCAL
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif

    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (int i = 1; i <= n; i++) {
        if (s[i] == '(')
            st.push(i);
        else {
            R[st.top()] = i, R[i] = st.top();
            st.pop();
        }
    }
    dfs(1, n);
    int ans = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            ans += f[1][n][i][j];
            ans %= mod;
        }
    }
    writeln(ans);
    return 0;
}

P6835【Cnoi2020】线形生物

期望 dp，做的很少，好不容易做一次。

积累的经验：

设 为 需要经过的期望距离，这样就可以表示 为 。（前缀和，原因是期望的线性性质，可以直接相加）

使用期望公式，，可以得到一条式子，通过将与 有关的全部放左边，其他的全部放右边，整理就可以得出一个可以递推的式子。

期望题目不要老想着数学做法，尝试 dp 套公式推式子做递推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

#define int long long

const int mod = 998244353;
const int maxn = 1e6 + 10;
struct Edge {
    int u, v;
}; std::vector<Edge> G[maxn];
int f[maxn], sum[maxn];

signed main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif

    int id, n, m;
    read(id, n, m);
    for (int i = 1; i <= m; i++) {
        static int u, v;
        read(u, v);
        G[u].push_back({u, v});
    }

    for (int i = 1; i <= n; i++) {
        f[i] = G[i].size() + 1;
        for (Edge e : G[i]) {
            f[i] += (sum[i - 1] - sum[e.v - 1]) % mod + mod; // 有可能是负数所以要加 mod
            f[i] %= mod;
        }
        sum[i] = sum[i - 1] + f[i];
        sum[i] %= mod;
    }
    writeln(sum[n]);
    return 0;
}

P2051【AHOI2009】中国象棋

二维 dp 很新颖的题目。

考虑每行枚举，向上通过统计上面一行状态来转移下面的状态。这种方法适用在不好统计重复的状态贡献（因为如果直接二维 dp 的话就不好控制两个方向上互相影响的贡献）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

#define int long long
const int mod = 9999973;
const int maxn = 200;
int f[maxn][maxn][maxn];
int C(int c) {
    return c * (c - 1) / 2;
}

signed main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif

    int n, m;
    read(n, m);
    f[0][0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= m; k++) {
                f[i][j][k] += f[i - 1][j][k]; f[i][j][k] %= mod;
                if (j >= 1) f[i][j][k] += f[i - 1][j - 1][k + 1] * (k + 1) % mod;
                if (k >= 1) f[i][j][k] += f[i - 1][j][k - 1] * (m - j - (k - 1)) % mod;
                if (k >= 2) f[i][j][k] += f[i - 1][j][k - 2] * C(m - j - (k - 2)) % mod;
                if (j >= 1) f[i][j][k] += f[i - 1][j - 1][k] * k * (m - (j - 1) - k) % mod;
                if (j >= 2) f[i][j][k] += f[i - 1][j - 2][k + 2] * C(k + 2) % mod;
                f[i][j][k] %= mod;
            }
        }
    }
    int ans = 0;
    for (int j = 0; j <= m; j++) {
        for (int k = 0; k <= m; k++) {
            ans += f[n][j][k]; ans %= mod;
            // writeln(j, k, f[n][j][k]);
        }
        // puts("");
    }
    writeln(ans);
    return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可