动态规划

本文最后更新于：星期四, 二月 3日 2022, 9:15 晚上

前缀和优化

P2511 [HAOI2008]木棍分割

f[i][j]=∑k=0min(i−1.j)f[i−1][j−k]f[i][j]=\sum_{k=0}^{min(i-1.j)}f[i-1][j-k]维护前缀和即可。

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

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define N 1010
const ll p = 10000;

int n, k;
ll f[N][N];

void RUN() {
    while (cin >> n >> k) {
        f[1][0] = 1ll;
        for (int i = 2; i <= n; ++i) {
            ll sum = 0;
            for (int j = 0; j <= k; ++j) {
                sum = (sum + f[i - 1][j]) % p;
                f[i][j] = sum;
                if (j >= i - 1) {
                    sum = (sum - f[i - 1][j - i + 1] + p) % p;
                }
            }
        }
        cout << f[n][k] << "\n";
    }
}


int main() {
#ifdef LOCAL_JUDGE
    freopen("input.txt", "r", stdin);
#endif

    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    RUN();

#ifdef LOCAL_JUDGE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}


单调队列优化

用于优化fi=min/max{gj}+wif_i=min/max\{g_j\}+w_i

前置技能 单调队列

单调队列性质

  • 队列中的元素其对应在原来的列表中的顺序必须是单调递增的。
  • 队列中元素的大小必须是单调递*(增/减/甚至是自定义也可以)

P1886 滑动窗口

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

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define N 1000010

struct node {
    int v, id;

    node() {}
    
    node(int id, int v) : id(id), v(v) {}
    
    void input(int _id) {
        id = _id;
        cin >> v;
    }
} a[N], q[N];

int n, k;

void RUN() {
    while (cin >> n >> k) {
        for (int i = 1; i <= n; ++i) {
            a[i].input(i);
        }
        int head = 1, tail = 0;
        for (int i = 1; i <= n; ++i) {
            while (head <= tail && q[tail].v >= a[i].v) {
                --tail;
            }
            q[++tail] = a[i];
            while (q[head].id <= i - k) {
                head++;
            }
            if (i >= k) {
                cout << q[head].v << " \n"[i == n];
            }
        }
        head = 1, tail = 0;
        for (int i = 1; i <= n; ++i) {
            while (head <= tail && q[tail].v <= a[i].v) {
                --tail;
            }
            q[++tail] = a[i];
            while (q[head].id <= i - k) {
                head++;
            }
            if (i >= k) {
                cout << q[head].v << " \n"[i == n];
            }
        }
    }
}

int main() {
#ifdef LOCAL_JUDGE
    freopen("input.txt", "r", stdin);
#endif

    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    RUN();

#ifdef LOCAL_JUDGE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}