CSES Dynamic Programming

这些是寒假集训新做的题，之前做过的不会再专门写一遍题解了，如果需要代码可以看仓库。

Longest Common Subsequence#

经典的 LCS，一个二维 DP 就可以解决，同时需要统计一下前驱，横着走和竖着走的时候不在 LCS 上，斜着走的时候在 LCS 上，最后输出。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 1010;
6
int f[N][N];
7
pair<int, int> pre[N][N];
8
int a[N], b[N];
9

10
void print(int i, int j) {
11
    if (!i) return;
12
    print(pre[i][j].first, pre[i][j].second);
13
    if (pre[i][j] == make_pair(i - 1, j - 1)) cout << a[i] << ' ';
14
}
15

16
int main() {
17
    ios::sync_with_stdio(0);
18
    cin.tie(0), cout.tie(0);
19
    int n, m;
20
    cin >> n >> m;
21
    for (int i = 1; i <= n; ++i) {
22
        cin >> a[i];
23
    }
24
    for (int i = 1; i <= m; ++i) {
25
        cin >> b[i];
26
    }
27
    for (int i = 1; i <= n; ++i) {
28
        for (int j = 1; j <= m; ++j) {
29
            if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1, pre[i][j] = {i - 1, j - 1};
30
            else if (f[i - 1][j] > f[i][j - 1]) f[i][j] = f[i - 1][j], pre[i][j] = {i - 1, j};
31
            else f[i][j] = f[i][j - 1], pre[i][j] = {i, j - 1};
32
        }
33
    }
34
    cout << f[n][m] << endl;
35
    print(n, m);
36
    cout << endl;
37
    return 0;
38
}

Minimal Grid Path#

刚开始只想着怎么 DP 出来一条路径，然后不是 TLE 就是 MLE，后来才发现事情远没有我想象的那么复杂。

从左上角开始贪心的选最小的，同步更新所有疑似是答案的路径。可行的 $O(n^2)$ 做法有沿着主对角线方向一层一层手动更新或者用单调队列bfs。我用了第一种，MoScenix用了第二种。

1
#include <iostream>
2

3
using namespace std;
4
const int N = 3010;
5
char a[N][N];
6
bool v[N][N];
7

8
int main() {
9
    ios::sync_with_stdio(0);
10
    cin.tie(0), cout.tie(0);
11
    int n;
12
    cin >> n;
13
    for (int i = 1; i <= n; ++i) cin >> (a[i] + 1);
14
    v[1][1] = true;
15
    cout << a[1][1];
16
    for (int k = 2; k < n * 2; ++k) {
17
        char mn = 'Z' + 1;
18
        for (int i = 1; i <= k; ++i) {
19
            int j = k - i;
20
            if (i < 0 || i > n || j < 0 || j > n) continue;
21
            if (!v[i][j]) continue;
22
            if (i < n) mn = min(mn, a[i + 1][j]);
23
            if (j < n) mn = min(mn, a[i][j + 1]);
24
        }
25
        cout << mn;
26
        for (int i = 1; i <= k; ++i) {
27
            int j = k - i;
28
            if (i < 0 || i > n || j < 0 || j > n) continue;
29
            if (!v[i][j]) continue;
30
            if (a[i + 1][j] == mn) v[i + 1][j] = true;
31
            if (a[i][j + 1] == mn) v[i][j + 1] = true;
32
        }
33
    }
34
    cout << endl;
35
    return 0;
36
}

Mountain Range#

~~根据直觉~~这个可以巧妙的转化成一个用一个中序遍历的序列生成一个二叉堆，求最大深度。这个问题就相当于在二叉堆上从上到下走到底的路径长度，需要注意如果一个节点和父亲节点权值一样那么这一条边不计入深度，因为不能平飞，用线段树维护出来区间最大值的位置就可以 $O(n\log n)$ 处理完。

1
#include <iostream>
2
#include <vector>
3
#include <tuple>
4

5
using namespace std;
6

7
typedef pair<int, int> PII;
8
const int N = 200010;
9
PII tr[N * 4];
10
int n;
11

12
PII merge(PII a, PII b) {
13
    if (a.first >= b.first) return a;
14
    else return b;
15
}
16

17
void pushup(int u) {
18
    tr[u] = merge(tr[u << 1], tr[u << 1 | 1]);
19
}
20

21
void modify(int u, int l, int r, int p, int v) {
22
    if (l == r) tr[u] = {v, l};
23
    else {
24
        int mid = l + r >> 1;
25
        if (p <= mid) modify(u << 1, l, mid, p, v);
26
        else modify(u << 1 | 1, mid + 1, r, p, v);
27
        pushup(u);
28
    }
29
}
30

31
PII query(int u, int l, int r, int ql, int qr) {
32
    if (ql > qr) {
33
        cout << "AWA" << endl;
34
    }
35
    if (ql <= l && r <= qr) return tr[u];
36
    else {
37
        int mid = l + r >> 1;
38
        PII res = {-1, -1};
39
        if (ql <= mid) res = merge(res, query(u << 1, l, mid, ql, qr));
40
        if (qr > mid) res = merge(res, query(u << 1 | 1, mid + 1, r, ql, qr));
41
        return res;
42
    }
43
}
44

45
int dp(PII rt, int l, int r) {
46
    if (l == r) return 1;
47
    int res = 1;
48
    if (l <= rt.second - 1) {
49
        PII ls = query(1, 1, n, l, rt.second - 1);
50
        res = max(res, dp(ls, l, rt.second - 1) + (rt.first > ls.first));
51
    }
52
    if (rt.second + 1 <= r) {
53
        PII rs = query(1, 1, n, rt.second + 1, r);
54
        res = max(res, dp(rs, rt.second + 1, r) + (rt.first > rs.first));
55
    }
56
    return res;
57
}
58

59
int main() {
60
    ios::sync_with_stdio(0);
61
    cin.tie(0), cout.tie(0);
62
    cin >> n;
63
    for (int i = 1; i <= n; ++i) {
64
        int t;
65
        cin >> t;
66
        modify(1, 1, n, i, t);
67
    }
68
    cout << dp(tr[1], 1, n) << endl;
69
    return 0;
70
}

Increasing Subsequence II#

也是比较经典的题，从求长度变成了求个数。初始化一个末尾是 0 的子序列个数是 1，离散化一下权值，用树状数组维护动态前缀和统计方案数。

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4

5
using namespace std;
6

7
const int N = 200010, MOD = 1000000007;
8
typedef long long LL;
9
vector<int> values;
10
int a[N], m;
11
LL tr[N];
12

13
int get(int x) {
14
    return lower_bound(values.begin(), values.end(), x) - values.begin() + 1;
15
}
16

17
void add(int x, LL v) {
18
    for (; x <= m; x += x & -x) {
19
        tr[x] = (tr[x] + v) % MOD;
20
    }
21
}
22

23

24
LL query(int x) {
25
    LL res = 0;
26
    for (; x; x -= x & -x) {
27
        res = (res + tr[x]) % MOD;
28
    }
29
    return res;
30
}
31

32
int main() {
33
    ios::sync_with_stdio(0);
34
    cin.tie(0), cout.tie(0);
35
    int n;
36
    cin >> n;
37
    for (int i = 1; i <= n; ++i) {
38
        cin >> a[i];
39
        values.emplace_back(a[i]);
40
    }
41
    values.emplace_back(0);
42
    sort(values.begin(), values.end());
43
    values.erase(unique(values.begin(), values.end()), values.end());
44
    m = values.size();
45
    for (int i = 1; i <= n; ++i) a[i] = get(a[i]);
46
    add(1, 1);
47
    LL res = 0;
48
    for (int i = 1; i <= n; ++i) {
49
        res = (res + query(a[i] - 1)) % MOD;
50
        add(a[i], query(a[i] - 1));
51
    }
52
    cout << res << endl;
53
    return 0;
54
}

Star's Blog

Longest Common Subsequence#

Minimal Grid Path#

Mountain Range#

Increasing Subsequence II#