发表更新27 分钟读完 (大约4000个字)

懵懂阶段梳理总结

[TOC]

动态规划

数字三角形模型

1
f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j]

e.g.摘花生

1015. 摘花生 - AcWing题库

1
2
3
4
5
6
7
8
9
10
f[0][1] = f[1][0] = 0;
f[0][2:end] = f[2:end][0] = -INF;

for i = 1:n, j = 1:m
4f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j];

f[n][m];

// f[0][1:m] = f[1:n][0] = 0;
// f[i][j] = f[i - 1][j] + f[i][j - 1] + 1;

e.g.最低通行费

1018. 最低通行费 - AcWing题库

1
2
3
4
5
6
7
f[0][1] = f[1][0] = 0;
f[0][2:end] = f[2:end][0] = INF;

for i = 1:n, j = 1:m
    f[i][j] = min(f[i - 1][j], f[i][j - 1]) + w[i][j];

f[n][m];

e.g.方格取数

1027. 方格取数 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int dx[4] = {-1, -1, 0, 0}, dy[4] = {-1, 0, -1, 0};

memset(f, 0, sizeof(f));
for (int k = 2; k <= 2 * n; k ++ )
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ ){
            if (k - i < 1 || k - i > n || k - j < 1 || k - j > n) continue;

            int t = w[i][k - i];
            if (i != j) t += w[j][k - j];
            for (int u = 0; u < 4; u ++ )
                f[k][i][j] = max(f[k][i][j], f[k - 1][i + dx[u]][j + dy[u]] + t);
        }
cout << f[2 * n][n][n] << endl;

最长上升子序列模型

e.g.怪盗基德的滑翔翼

1017. 怪盗基德的滑翔翼 - AcWing题库

单调子序列的最大长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int res = -INF;
for (int i = 1; i <= n; i ++ ){
    f[i] = 1;
    for (int j = 1; j < i; j ++ )
        if (a[i] > a[j])
            f[i] = max(f[i], f[j] + 1);
    res = max(res, f[i]);
}
for (int i = n; i >= 1; i -- ){
    f[i] = 1;
    for (int j = n; j > i; j -- )
        if (a[i] > a[j])
            f[i] = max(f[i], f[j] + 1);
    res = max(res, f[i]);
}
cout << res << endl;

e.g.登山

1014. 登山 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for (int i = 1; i <= n; i ++ ){
    f[i] = 1;
    for (int j = 1; j < i; j ++ )
        if (a[i] > a[j])
            f[i] = max(f[i], f[j] + 1);
}
for (int i = n; i >= 1; i -- ){
    g[i] = 1;
    for (int j = n; j > i; j -- )
        if (a[i] > a[j])
            g[i] = max(g[i], g[j] + 1);
}

int res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, f[i] + g[i] - 1);
cout << res << endl;

e.g.友好城市

1012. 友好城市 - AcWing题库

应用题

e.g.最大上升子序列和

1016. 最大上升子序列和 - AcWing题库

上升子序列的最大价值

1
2
3
4
5
6
7
8
9
int res = -INF
for (int i = 0; i < n; i ++ ){
    f[i] = w[i];
    for (int j = 0; j < i; j ++ )
        if (w[i] > w[j])
            f[i] = max(f[i], f[j] + w[i]);
    res = max(res, f[i]);
}
cout << res << endl;

e.g.拦截导弹

1010. 拦截导弹 - AcWing题库

Dilworth定理：将一个序列划分成若干个单调不升子序列的最小个数等于该序列最长上升子序列的个数

另有贪心作法，XXXX

e.g.导弹防御系统

187. 导弹防御系统 - AcWing题库

XXXX

e.g.最长公共上升子序列

272. 最长公共上升子序列 - AcWing题库

遍历时一并记录之前的满足大小条件的最大长度

1
2
3
4
5
6
7
8
9
10
11
int res = 0;
for (int i = 1; i <= n; i ++ ){
    int tmp = 1;
    for (int j = 1; j <= n; j ++ ){
        f[i][j] = f[i - 1][j];
        if (a[i] > b[j]) tmp = max(tmp, f[i - 1][j] + 1);
        if (a[i] == b[j]) f[i][j] = max(f[i][j], tmp);
        if (i == n) res = max(res, f[i][j]);
    }
}
cout << res << endl;

背包模型

有背包体积$m$，$n$个待决策的物品，每个物品对应有体积$v_i$、价值$w_i$，

对每个物品的决策可能是：选择加入背包、选择不加入背包，

求，对于所有决策可能，背包（中各个物品的集体）的最大价值。

1
2
3
4
5
6
7
8
9
10
11
12
13
int n, m;
int v[N], w[N]; // 1 ~ n
int f[N][M]; // (1 ~ n, 0 ~ m)

for (int i = 0; i <= m; i ++ ) f[0][i] = 0;

for (int i = 1; i <= n; i ++ )
    for (int j = 0; j <= m; j ++ ){
        f[i][j] = f[i - 1][j];
        if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
    }

cout << f[n][m] << endl;

费用情况

以求方案数为例：

限定费用上限；

1
2
3
4
5
6
7
for (int i = 0; i <= m; i ++ ) f[0][i] = 1;

for (int i = 1; i <= n; i ++ )
   4for (int j = 0; j <= m; j ++ ){
        f[i][j] = f[i - 1][j];
        if (j >= v[i]) f[i][j] += f[i - 1][j - v[i]];
    }

限定费用为定值；

1
2
3
4
5
6
7
8
for (int i = 1; i <= m; i ++ ) f[0][i] = 0;
f[0][0] = 1;

for (int i = 1; i <= n; i ++ )
   4for (int j = 0; j <= m; j ++ ){
        f[i][j] = f[i - 1][j];
        if (j >= v[i]) f[i][j] += f[i - 1][j - v[i]];
    }

限定费用下限；

1
2
3
4
5
6
7
8
for (int i = 1; i <= m; i ++ ) f[0][i] = 0;
f[0][0] = 1;

for (int i = 1; i <= n; i ++ )
    for (int j = 0; j <= m; j ++ ){
        f[i][j] = f[i - 1][j];
        f[i][j] += f[i - 1][max(0, j - v[i])];
    }

购买次数

各物品均限购一次；

1
2
3
4
5
for (int i = 1; i <= n; i ++ )
    for (int j = 0; j <= m; j ++ ){
        f[i][j] = f[i - 1][j];
        if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
    }

购买次数不限；

1
2
3
4
5
6
7
8
9
10
for (int i = 1; i <= n; i ++ )
    for (int j = 0; j <= m; j ++ ){
        f[i][j] = f[i - 1][j];
        if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
    }
/*
f[i][j] = max{f[i - 1][j], f[i - 1][j - v[i]] + w[i] ..., f[i - 1][j - maxk * v[i]] + maxk * w[i]};
f[i][j - v[i]] = max{f[i - 1][j - v[i]], ..., f[i - 1][j - maxk * v[i]] + (maxk - 1) * w[i]};
f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
*/

各物品限购不同次数：

①，二进制$O(n\times log_2s)$预处理各物品，物品维最多变为$O(n\times log_2s)$，之后正常按限购一次处理，总时间复杂度即为$O(n\times log_2s\times V)$

1
2
3
4
5
6
7
8
9
10
11
12
13
p.push_back({0, 0});
while (n -- ){
    int v, w, s;
    cin >> v >> w >> s;

    int t = 1;
    while (t <= s){
        p.push_back({t * v, t * w});
        s -= t;
        t <<= 1;
    }
    if (s) p.push_back({s * v, s * w});
}

②，单调队列$O(1)$取得滑动窗口最值，总时间复杂度$O(n\times V)$

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 1; i <= n; i ++ )
    for (int j = 0; j < v[i]; j ++ ){
        hh = 0, tt = -1;
        for (int k = j; k <= m; k += v[i]){
            if (hh <= tt && q[hh] < k - s[i] * v[i]) hh ++ ; // when to pop_front
            while (hh <= tt && f[i - 1 & 1][q[tt]] - (q[tt] - j) / v[i] * w[i] <= f[i - 1 & 1][k] - (k - j) / v[i] * w[i]) tt -- ; // when to pop_back
            q[ ++ tt] = k; // push
            f[i & 1][k] = f[i - 1 & 1][q[hh]] + (k - q[hh]) / v[i] * w[i]; // front
        }
    }

printf("%d\n", f[n & 1][m]);

状态压缩

每个当前状态f[i][j]的计算，使用到的是在物品维下的相邻前项的所有状态f[i - 1][0: m]，即每次状态计算仅使用到上一个物品的体积维。每次状态计算中，物品维仅需记录一项，故可消去物品维。

每次计算使用到的是体积维中的前项，属于体积维中还未计算的状态，故状态计算遍历时，体积维需逆序。

1
2
3
4
5
6
7
8
9
int f[M]; // 0 ~ m

for (int i = 0; i <= m; i ++ ) f[i] = 0;

for (int i = 1; i <= n; i ++ )
   4for (int j = m; j >= v; j -- )
        f[j] = max(f[j], f[j - v[i]] + w[i]);

cout << f[m] << endl;

二维费用

1
2
3
4
for (int i = 1; i <= n; i ++ )
    for (int j = V1; j >= v1[i]; j -- )
        for (int k = V2 - 1; k >= v2[i]; k -- )
            f[j][k] = max(f[j][k], f[j - v1[i]][k - v2[i]] + w[i]);

具体方案

物品维从大到小递推，求方案时就能从小到大反推，并且能选则选，即可得字典序最小方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for (int i = n; i >= 1; i -- )
    for (int j = 0; j <= m; j ++ ){
        f[i][j] = f[i + 1][j];
        if (j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
    }

int p = m;
bool flag = false;
for (int i = 1; i <= n; i ++ )
    if (p >= v[i] && f[i][p] == f[i + 1][p - v[i]] + w[i]){
        if (!flag){
            cout << i;
            flag = true;
        }
        else cout << ' ' << i;
        p -= v[i];
    }
cout << endl;

e.g.宠物小精灵之收服

1022. 宠物小精灵之收服 - AcWing题库

最优价值下的最高剩余费用

1
2
3
4
5
6
7
8
for (int i = 1; i <= n; i ++ )
    for (int j = V1; j >= v1[i]; j -- )
        for (int k = V2 - 1; k >= v2[i]; k -- )
            f[j][k] = max(f[j][k], f[j - v1[i]][k - v2[i]] + 1);
cout << f[V1][V2 - 1] << ' ';
int p = V2 - 1;
while (p && f[V1][p - 1] == f[V1][V2 - 1]) p -- ;
cout << V2 - p << endl;

e.g.货币系统

来源：532. 货币系统 - AcWing题库

遍历时计算得下一个物品是否可被前部物品组表示

1
2
3
4
5
6
7
8
9
10
11
12
sort(a + 1, a + n + 1);

int res = 0;
m = a[n];
memset(f, 0, sizeof(f));
f[0] = true;
for (int i = 1; i <= n; i ++ ){
    if (!f[a[i]]) res ++ ;
    for (int j = a[i]; j <= m; j ++ )
        f[j] |= f[j - a[i]];
}
printf("%d\n", res);

e.g.混合背包

7. 混合背包问题 - AcWing题库

对于多重背包，用二进制优化处理为普通背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
while (n -- ){
    int v, w, s;
    cin >> v >> w >> s;
    if (s == 0){
        for (int j = v; j <= m; j ++ )
            f[j] = max(f[j], f[j - v] + w);
    }
    else{
        if (s == - 1) s = 1;
        for (int k = 1; k <= s; k <<= 1){
            for (int j = m; j >= k * v; j -- )
                f[j] = max(f[j], f[j - k * v] + k * w);
            s -= k;
        }
        if (s){
            for (int j = m; j >= s * v; j -- )
                f[j] = max(f[j], f[j - s * v] + s * w);
        }
    }
}
cout << f[m] << endl;

e.g.有依赖的背包问题

10. 有依赖的背包问题 - AcWing题库

由于是深搜序，计算f[u][j]时，各子节点的f[son][0:m]都已算好。

遍历当前子节点的过程即相当于物品维限定在当前各子节点上，求考虑所有当前子节点下的最优价值，用滚动数组（备份数组）节省空间。

每次以分配给各单层子节点的体积做决策，视作分组背包过程，该父节点u在各体积j下的对各子节点的最优决策价值记在f[u][j]中，该价值又可能被更上一层（相对当前子节点来说的祖父层）用做分配以体积j所对应的最大价值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs(int u){
    for (int i = h[u]; ~i; i = ne[i]){
        int son = e[i];
        dfs(son);
        
        memcpy(g, f, sizeof(f));
        for (int j = 0; j <= m - v[u]; j ++ )
            for (int k = 0; k <= j; k ++ ) // 相当于分组背包的决策层，以所分配的体积作决策
                f[u][j] = max(f[u][j], g[u][j - k] + f[son][k]);
    }
    memcpy(g, f, sizeof(f));
    for (int i = 0; i <= m; i ++ )
        if (i < v[u]) f[u][i] = 0;
        else f[u][i] = g[u][i - v[u]] + w[u];
}

e.g.背包问题求方案数

11. 背包问题求方案数 - AcWing题库

所求的是对应最优价值的所有方案数。f与g的含义都是在限定费用上限的意义下的。

1
2
3
4
5
6
7
8
9
for (int i = 0; i <= m; i ++ ) g[i] = 1;
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            if (f[j] < f[j - v[i]] + w[i]){
                f[j] = f[j - v[i]] + w[i];
                g[j] = g[j - v[i]];
            }
            else if (f[j] == f[j - v[i]] + w[i]) g[j] = (LL)(g[j] + g[j - v[i]]) % mod;
cout << g[m] << endl;

e.g.能量石

734. 能量石 - AcWing题库

决策内容包括选择哪些物品及选择顺序，可以发现最优解对应的物品选择顺序必定需要符合所发现的序。

f[i][j]表示考虑前i个物品，最终位于j时刻情况下的最优价值

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 110, M = 10010;

int n;
struct Node{
    int s, e, l;
    
    bool operator<(const Node &W)const{
        return s * W.l < W.s * l;
    }
}p[N];
int f[M];

int main(){
    int T;
    scanf("%d", &T);
    for (int C = 1; C <= T; C ++ ){
        scanf("%d", &n);
        int m = 0;
        for (int i = 1; i <= n; i ++ ){
            scanf("%d %d %d", &p[i].s, &p[i].e, &p[i].l);
            m += p[i].s;
        }
        sort(p + 1, p + n + 1);
        
        memset(f, -0x3f, sizeof(f));
        f[0] = 0;
        for (int i = 1; i <= n; i ++ )
            for (int j = m; j >= p[i].s; j -- )
                f[j] = max(f[j], f[j - p[i].s] + p[i].e - (j - p[i].s) * p[i].l);
        int res = 0;
        for (int i = 0; i <= m; i ++ ) res = max(res, f[i]);
        printf("Case #%d: %d\n", C, res);
    }
    
    return 0;
}

e.g.金明的预算方案

487. 金明的预算方案 - AcWing题库

属于有依赖的背包问题，但依赖关系简单且最多有2个子节点，故可依子节点选择情况枚举遍历，视作一种分组背包。

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
#include <iostream>
#include <algorithm>
#include <vector>

#define v first
#define w second

using namespace std;

typedef pair<int, int> PII;

const int N = 110, M = 4e4 + 10;

int n, m;
PII mas[N];
vector<PII> ser[N];
int f[M];

int main(){
    cin >> m >> n;
    for (int i = 1; i <= n; i ++ ){
        int v, w, p;
        cin >> v >> w >> p;
        if (!p) mas[i] = {v, v * w};
        else ser[p].push_back({v, v * w});
    }
    
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= 0; j -- ){
            int sz = ser[i].size();
            for (int k = 0; k < 1 << sz; k ++ ){
                int v = mas[i].v, w = mas[i].w;
                for (int u = 0; u < sz; u ++ )
                    if (k >> u & 1){
                        v += ser[i][u].v;
                        w += ser[i][u].w;
                    }
                if (j >= v) f[j] = max(f[j], f[j - v] + w);
            }
        }
    cout << f[m] << endl;
    
    return 0;
}

状态机模型

e.g.大盗阿福

1049. 大盗阿福 - AcWing题库

1
2
3
4
5
6
7
8
9
10
f[0][0] = 0;
f[0][1] = -1e9;
for (int i = 1; i <= n; i ++ ){
    int t;
    cin >> t;

    f[i & 1][0] = max(f[i - 1 & 1][0], f[i - 1 & 1][1]);
    f[i & 1][1] = f[i - 1 & 1][0] + t;
}
cout << max(f[n & 1][0], f[n & 1][1]) << endl;

e.g.股票买卖 IV

1057. 股票买卖 IV - AcWing题库

1
2
3
4
5
6
7
8
9
10
memset(f, -0x3f, M * 2 * 4);
for (int i = 0; i <= n - 1; i ++ ) f[i][0][0] = 0;
for (int i = 1; i <= n; i ++ )
    for (int j = 1; j <= m; j ++ ){
        f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + a[i]);
        f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - a[i]);
    }
int res = 0;
for (int i = 0; i <= m; i ++ ) res = max(res, f[n][i][0]);
cout << res << endl;

e.g.股票买卖 V

1058. 股票买卖 V - AcWing题库

0：待卖；1：冻结待买；2：自由待买

1
2
3
4
5
6
7
8
f[0][0] = f[0][1] = -1e9;
f[0][2] = 0;
for (int i = 1; i <= n; i ++ ){
    f[i][0] = max(f[i - 1][0], f[i - 1][2] - a[i]);
    f[i][1] = f[i - 1][0] + a[i];
    f[i][2] = max(f[i - 1][2], f[i - 1][1]);
}
cout << max(f[n][1], f[n][2]) << endl;

状态压缩模型

e.g.蒙德里安的梦想

来源：291. 蒙德里安的梦想 - AcWing题库

XXXX

线性DP

e.g.编辑距离

来源：899. 编辑距离 - AcWing题库

XXXX

区间DP

树形DP

数位DP

e.g.整数划分

来源：900. 整数划分 - AcWing题库

XXXX

图论

搜索

e.g.奶牛选美

来源：2060. 奶牛选美 - AcWing题库

XXXX

e.g.拖拉机

来源：2019. 拖拉机 - AcWing题库

XXXX

e.g.贝茜的复仇

来源：1875. 贝茜的报复 - AcWing题库

XXXX

连通性

拓扑序

最短路

MST

二分图

数据结构

单调队列

e.g.滑动窗口

来源：154. 滑动窗口 - AcWing题库

XXXX

并查集

e.g.食物链

来源：240. 食物链 - AcWing题库

XXXX

e.g.银河英雄传说

来源：238. 银河英雄传说 - AcWing题库

XXXX

字典树

e.g.最大异或对

来源：143. 最大异或对 - AcWing题库

XXXX

线段树

e.g.一个简单的整数问题2

来源：243. 一个简单的整数问题2 - AcWing题库

XXXX

平衡树

树状数组

e.g.一个简单的整数问题2

来源：243. 一个简单的整数问题2 - AcWing题库

XXXX

数学

快速幂

XXXX

费马小定理

对于整数a、p，若p是质数且a不是p的倍数，那么有$a^{p-1}=1(mod~p)$成立。

等式左边同分出一个a，则有$a\cdot a^{p-2}=1$，从而有：**对于给定质数p，所有不是p倍数的整数a的模p逆元为a的p-2次方$a^{p-2}$**。

e.g.爬树的甲壳虫

来源：2022年4月第十三届蓝桥杯C/C++程序设计A组（省赛）

XXXX

扩展欧几里得

矩阵乘法

博弈

基础算法

贪心

e.g.区间选点

来源：905. 区间选点 - AcWing题库

XXXX

e.g.货仓选址

来源：104. 货仓选址 - AcWing题库

XXXX

e.g.耍杂技的牛

来源：125. 耍杂技的牛 - AcWing题库

XXXX

差分

离散化

二分

XXXX

e.g.青蛙过河

来源：2022年4月第十三届蓝桥杯C/C++程序设计A组（省赛）

XXXX

e.g.粉刷栅栏

来源：1987. 粉刷栅栏 - AcWing题库

XXXX

e.g.金发姑娘和N头牛

来源：1952. 金发姑娘和 N 头牛 - AcWing题库

XXXX

e.g.救生员

来源：1750. 救生员 - AcWing题库

XXXX

双指针

e.g.愤怒的奶牛

来源：1855. 愤怒的奶牛 - AcWing题库

位运算

高精度

其他

手动O2优化

#pragma GCC optimize(2,”inline”)

e.g.岛

来源：2014. 岛 - AcWing题库

XXXX

懵懂阶段梳理总结

https://diaackr.github.io/2022/11/11/懵懂阶段总结/

作者

DIaacKr

发布于

2022-11-11

更新于

2023-01-16

许可协议

#
关注我

链接

分类

最新文章

归档

标签

blog1
brand-new1
hexo-learning3
icarus1
md-learning1
动态规划1
图论1
基础算法1
数学1
数据结构1
×