Skip to content

第一讲 数学基础

before: 多组输入的处理

输入处理

  • 类型一：输入不说明有多少input block，默认以EOF为读入结束

例1：A+B Problem

#include <stdio.h>
int main()
{
    int a, b;
    while(scanf("%d %d", &a, &b) != EOF) 
        printf("%d\n", a + b);
    return 0;
}

scanf函数的返回值为成功输入的变量个数，无读入返回EOF（为-1，而非0），因而我们还可以这样：

#include <stdio.h>
int main()
{
    int a, b;
    while(scanf("%d %d", &a, &b) == 2) 
        printf("%d\n", a + b);
    return 0;
}

若使用cpp，更加方便

while(cin >> a >> b) {
    ...
}

  • 类型二：输入开始告知有N个Input Block

先读入N，在借助while或者for循环实现

  • 类型三：不说明有多少Input Block，但是以特殊输入为结束标志

处理方式类似类型一——先读

仍然以A+B Problem为例，当a与b均不为0时结束

#include <stdio.h>
int main()
{
    int a, b;
    while(scanf("%d %d", &a, &b) != EOF && (a != 0 || b != 0)) 
        printf("%d\n", a + b);
    return 0;
}

更好地：（可读性更好）

while(scanf("%d %d", &a, &b)) {
    if(a == 0 && b == 0)    break;
    printf("%d\n", a + b);
}

  • 类型四：前三种的组合问题

  • 类型五：字符串的输入问题

例：HDOJ_1048

若c：

char buf[20];
gets(buf);
// 不安全的读入，不推荐！

若cpp：

//如果用 string buf; 来储存
getline(cin, buf);
//如果用 char buf[255]; 来保存
cin.getline(buf, 255); //cin的成员函数

输出处理

  • 类型一：每个Input Block对应一个Output Block，Output Block之间没有空行

  • 类型二：每个Input Block对应一个Output Block，Output Block之后有一个空行

  • 类型三：每个Input Block对应一个Output Block，Output Block之间有一个空行

小差别注意即可

注意：

多组数据，是否需要一次性全部读取，再一组一组处理？

不需要

提交到OJ的程序从文件中读取，然后生成临时文件存储输出，与标准Output进行逐字符对比处理

导引：整数求和($N \leq 500000$)

  • 等差数列的公式求和的风险？

$sum(n) = n \times (n - 1) / 2$，N过大时，$n \times (n-1)$会爆int(32位) 解决方案：

  • 64位整数(long long, %lld)

例一：求最小公倍数

  • 暴力枚举？TLE

  • 数学方法：$LCM(A,B)=A \times B/GCD(A,B)$

注意点同导引，如何防止过程中爆int？先÷后x

$LCM(A,B)=A/GCD(A,B) \times B$

  • 求GCD？辗转相除法（欧几里得算法）

  • $O(\log n)$级的算法

  • 原理
  • 终止条件：有一方为0，另一方为gcd

cpp int gcd(int a, int b) { int temp; while(b != 0) { temp = a % b; a = b; b = temp; } return a; }

​ 为什么不需要在意大小？第一轮处理会交换

cpp //递归写法 int gcd(int a, int b) return (b != 0) ? gcd(b, a % b) : a;

例二：计算N个N相乘的个位数——规律

  • （$1 \leq N \leq 1,000,000,000$)
  • 暴力（TLE）
  • 每次处理后模10？——解决了数据溢出，但是循环次数仍然太多
  • 找到规律循环节，后打表

为什么去找规律？

  • 数据规模太大
  • 暴力计算不可行

例三：特别的fibonacci数列——规律与循环节

$F(0) = 7$

$F(1) = 11$

$F(n) = F(n-1)+F(n-2)\quad(n > 3)$

给定一个n(n<1000000)，请判断F(n)能否被3整除，分别输出yes和no

  • 递归计算每一项，模3 数据规模太大

  • 同余定理：$F(n)\%3=F(n-1)\%3+F(n-2)\%3$

  • 规律：发现循环节

G(1) G(2) G(3) G(4) G(5) G(6) G(7) G(8) G(9) G(10) G(11)
1 2 0 2 2 1 0 1 1 2 0

循环节为8

  • 为什么一定会有循环节？

——抽屉原理

由于%3结果一定是0 1 2，且前两项导出后一项，考虑所有相邻两项的组合，共有9种组合，且0 0情况可排除，即8种，则根据抽屉原理（容斥原理），则循环节在大致9位内会出现，一旦出现了重复的相邻两项，则一定出现了循环节

例四：求A^B最后三位数表示的整——快速幂

  • 找规律不可行 样本太大了

  • 快速幂（二分加速）

  • 递归实现

    cpp int power(int a, int n) { int ans; if(n == 0) ans = 1; else { ans = power(a * a, n / 2); if(n % 2 == 1) ans *= a; } return ans; }

  • 非递归实现

    cpp int power(int a, int n) { int ans = 1; while(n) { if(n % 2) ans *= a; a = a * a; n /= 2; } return ans; }

  • 特别注意：小心爆int!!

  • 快速幂基本都伴随着取模运算

第二讲 贪心算法

  • 总是做出当前来看的最优解
  • 分解子问题，对子问题按照同样的策略进行操作

例一：田忌赛马

已知田忌与国王所有马的能力值，赢的人获得200元，如何找到最优解？

  • 贪心策略

用自己的马挑战对方比自己弱的最小的马

  • 确定思路

  • 排序

  • 比较未标记的最好的马，自己的能超过对方的马吗
    • 如果可以，则赛马
    • 如果不可以，则用自己最差的马和对方最好的马赛马
    • 赛马做标记
  • 重复策略直至所有的马比完

例二：事件序列问题

  • 贪心策略

拿结束时间排序，尽量留出更多的时间

  • 确定思路

  • 提出命题：至少存在一个最长的事件序列，包含最早结束的事件

    • 证明：反证法

    逆命题：所有的最长事件序列都不包含最早结束的事件

    在该假设下任取一个最长的事件序列，将第一个事件与最早结束的事件替换，则构造了一个相同长度的最长的时间序列且含有最早结束的事件，逆命题不成立，原命题得证

  • 按照结束时间排序

  • 找到最早结束事件作为第一个事件

    此时问题分解为n-1阶的子问题，注意额外分析是否会冲突

  • 注意！！选出的结果方案不唯一，而方案的序列长度一定唯一

例三：搬桌子

丁爸信奥培训中心最近在富丽科技大厦租了一层楼，这层楼的形状如下： img

由图可见，这层楼中间是走廊，两侧各有200个房间，编号如上图。

最近，丁爸信奥培训中心做了内部机构的调整，需要把一些桌子从一个房间搬到另外的房间。因为走廊很窄，但是桌子很大，所以同一段走廊每次只能通过一个桌子。 假设不论远近，每趟搬桌子都需要10分钟。同时，当你从房间i搬桌子到房间j的过程中，房间i到房间j之间的走廊都被占用，也就是说，在每个10分钟内，不能有多个任务共享同一段走廊。

现在，丁爸想知道：要完成所有的搬运任务，最少需要多少时间？

  • 问题分析：

  • 为什么不能找多次最长事件序列？

    最长事件序列只能保证单一最优解，全局并非最优解

  • 贪心策略

  • 最优策略：记录路径，找到重叠最多地方的重叠次数，即为所需最多的次数

    ```cpp

    include

    include

    include

    using namespace std; int p[201]; int main() { int T, ans; cin >> T; while(T --) { int n; cin >> n; int s,t; memset(p, 0, sizeof(p)); ans = 0; for(int i = 0; i < n; i ++) { cin >> s >> t; s = (s + 1) / 2; t = (t + 1) / 2; if(s > t) swap(s, t); for(int j = s; j <= t; j++) p[j]++; } for(int i = 1; i <= 200; i ++) if(p[i] > ans) ans = p[i]; cout << ans * 10 << endl; } return 0; } ```

  • 较差策略：按照开始位置排序，从第一个需要搬的桌子开始i，一次性找到所有线路不冲突的桌子，不断分解子问题

    ```cpp

    include

    include

    include

    include

    using namespace std; struct M{ int s; int t; };

    bool comp(const M &m1, const M &m2){ return m1.s < m2.s; //按照开始的房间号排序 }

    int main(){ int T, s, t; scanf("%d", &T); while(T--) { int n; vector v; scanf("%d", &n); for(int i = 0; i < n; ++i) { M m; scanf("%d%d", &s, &t); if(s > t)//有可能从号码大的房间往回搬，若是，则交换s与t swap(s, t); m.s = s; m.t = t; v.push_back(m); } sort(v.begin(), v.end(), comp); int ans = 0; for(vector::iterator it = v.begin(); it != v.end();){ //从房间号最小的开始查找 ++ans; int t = (it).t; for(vector::iterator subit = it; subit != v.end();) { //找到与要搬的线路不冲突的桌子 if((subit).s > t && !((subit).s - t == 1 && (subit).s % 2 == 0)) { //注意对面房间的线路也是冲突的，比如5与6 t = (*subit).t; subit = v.erase(subit); //该桌子已搬完，删除 } else ++subit; //否则继续查找下一张桌子 } it = v.erase(it); //删除 } printf("%d\n", ans * 10); } return 0; }

    ```

例四：删数问题

有一个长度为n（n <= 240）的正整数，从中取出k（k < n）个数，使剩余的数保持原来的次序不变，求这个正整数经过删数之后最小是多少。

  • 子问题分解：每一次删除数字都使得剩下的正整数保持最小

  • 贪心策略：

删除从左向右第一个逆序列的第一个数字

或 删除从左到右递增序列结束处的数字

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

int main() {
    string str;
    int k, flag = 0;
    vector<char> v;

    cin >> str >> k;

    for(int i = 0;  i < str.size(); i++){
        v.push_back(str[i]);
    } 

    while(k--){
        int i = 0;
        flag = 0;
        vector<char>:: iterator t = v.begin();  //这里主要是为了调用  v.erase()的库函数删除元素
        while(i != v.size() - 1) {  //注意这里的减一 因为下方的v[i+1] 否则会出现段错误
            if(v[i] > v[i + 1]) {  //如果出现后一个数小于前一个数那么这就是这一趟的递增的终点 
                v.erase(t);
                flag = 1;
                break;
            }
            i++;
            t++;
        }

        if(flag == 0) {//如果是一个递增序列那么的话就要删除最后一个数 
            v.erase(t);
        }        
    } 
    int i = 0;
    //这么输出是为了防止前置'0'的输出
    for(int i = 0; i < v.size(); i++)  {
        if(v[i] != '0')
            break; 
    }   
    for(int j = i; j < v.size(); j++){
        cout << v[j];
    }   
}

例五：青蛙的邻居

未名湖附近共有N个大小湖泊L1, L2, ..., Ln(其中包括未名湖)，每个湖泊Li里住着一只青蛙Fi(1 ≤ i ≤ N)。如果湖泊Li和Lj之间有水路相连，则青蛙Fi和Fj互称为邻居。现在已知每只青蛙的邻居数目x1, x2, ..., xn，请你给出每两个湖泊之间的相连关系。

Input

第一行是测试数据的组数T(0 ≤ T ≤ 20)。每组数据包括两行，第一行是整数N(2 < N < 10)，第二行是N个整数，x1, x2,..., xn(0 ≤ xi ≤ N)。

Output

对输入的每组测试数据，如果不存在可能的相连关系，输出"NO"。否则输出"YES"

  • 离散数学：可图形判定

  • 度序列

    若把一个图G所有顶点的度数台城一个序列S，则称S为图G的度序列

  • 度序列是可图的

    一个非负整数组成的有限序列如果是某个无向图的度序列，则称该序列是可图的

  • Havel-Hakimi定理

    由非负整数组成的有限非递增序列，$S={d1,d2,d3...dn}$，当且仅当$S1={d2-1,d3-1...d(d1+1),d(d1+2)......dn}$也是可图的

  • 贪心策略：

通过havel-hakimi定理，对序列由大到小排序，然后对$S_1$操作，排序，对$S_2$操作，排序……直到序列全部变成0。如果出现负数，则该度序列是不可图的

第三讲 并查集

导引问题

在某个城市里住着n个人，现在存在关于n个人的m条信息，假设所有认识的人为一个单位，最多有多少个单位

什么是并查集

  • Disjoint Set，即“不相交的集合”

N个元素的N个对象划分为不相交集合，每个集合中选定某个元素代表所在集合

  • 常见两种操作
  • 合并两个集合
  • 查找某个元素属于哪个集合

实现方法一

  • 用编号最小的元素标记所在集合

  • 定义一个数组$Set[1..n]$，其中$Set[i]$表示元素$i$所在集合

Set(i) 1 2 1 4 2 6 1 6 2 2
i 1 2 3 4 5 6 7 8 9 10

不相交集合：

${1, 3, 7}, {4}, {2, 5, 9, 10}, {6, 8}$

  • 两个功能

  • 查 $O(1)$

    cpp int find(x) return Set[x];

  • 并 $O(n)$

    cpp void Merge(a, b) { int i = min(a, b); int j = max(a, b); for(int k = 1; k <= N; k++) { if(Set[k] = j) Set[k] = i; } }

实现方法二——树

  • 利用树实现
  • 定义数组$Set[1..n]$
  • 若$Set[i] = i$，说明$i$表示该集合，是该集合的对应树的根

  • 若$Set[i] = j$，说明$j$是$i$的父节点

  • 两个功能

  • 查 最坏$O(n)$

    cpp int find(x) { int r = x; while(Set[r] != r) r = Set[r]; return r; }

  • 并 $O(1)$

    cpp void merge(a, b) Set[a] = b;

  • 避免出现最坏情况

    • 方法：将深度小的树合并到深度大的树

    • 实现：假设两棵树的深度$h_1$,$h_2$，则合并后的树的高度为

    $h = \begin{cases} \max(h_1, h_2) & \text{if } h_1 \neq h_2 \ h_1+1 & \text{if } h_1=h_2 \end{cases}$

    • 效果：任何顺序的合并操作后，包含k个节点的树的最大高度不超过$\log k$

  • 优化后

    cpp void merge(a, b) { if(height[a] = height[b]) { height[a]++; Set[b] = a; } else if(height(a) < height(b)) Set[a] = b; else Set[b] = a; }

    此时，查的效率已经变为最坏$O(\log n)$

实现方法三——带路径压缩的查找操作

int find(x) {
    if(Set[x] != x)
        Set[x] = find(Set[x]);
    return Set[x];
}

例一

经典案例：最小生成树

  • Prim算法

  • Kruskal算法

  • 理论基础——MST性质

    命题：至少存在一颗最小生成树含有权值最小的边

​ 证明：类似第二讲例二的证明

  • 算法步骤：（贪心算法）
    • 选中最小的边
    • 找到下一个最小的边，若两个顶点不连通，则选中，重复
    • 直到选中$n-1$条边

例二

第四讲 递推求解

  • 递推关系式（状态转移方程）

将$F(n)$用$F(n-1)$与增减量表示 可能与前面的多项有关系

例一——状态产生分析

一个平面上有$n$条直线，这些直线中每一条在圆内同其他直线相交，假设没有三条直线相交，试问能分成多少区域

  • 分析：假设此时有n-1条直线分割圆，令第n条直线把上述n-1条直线分割产生n-1个端点，n条线段，即可分割产生n个新区域

初始状态：$F(1)=2$

状态转移方程：$F(n)=F(n-1)+n$

例二

平面上有$n$条折线，这些折线最多能将平面分割为多少块？

  • 分析：假设此时有n-1条直线分割平面，第n条折线可以做到与前n-1条折线都产生四个交点

状态转移方程：$F(n)=F(n-1)+4(n-1)+1$

例三——状态向前分析

在$2\times n$的长方形方格中，用n个$1\times 2$的骨牌铺满方格，有多少种铺设的方案

  • 例一与例二都是从状态产生的角度去思考状态转移方程

  • 然而 例三给出了另一种思考方式

从第$n$个状态向前分析成因

第n列格子分为横竖两种状态

若为竖，则前有F(n-1)种状态

若为横，则n列和n-1列为双横，前有F(n-2)种状态，故：

状态转移方程：$F(n)=F(n-1)+F(n-2)$

  • 核心：大问题分类讨论分别解决

例四

有$1 \times n$的长方形，用$1\times 1$，$1\times 2$，$1\times 3$的骨牌铺满方格，求第n个多少种铺法

  • 分析同例三

状态转移方程：$F(n)=F(n-1)+F(n-2)+F(n-3)$

总结

  • 首先：确认能否容易得到初始状态的解
  • 假设：规模不大于$N-1$的状态已经得到了解决
  • 最后：重点分析当规模扩大到$N$时，如何枚举当前的情况，然后用子问题生成

例五——合法性角度分类

所有学生站成一排，规定女孩不能单独站，即要么队列中没有女生，要么不止一个女生并排站

比如，$n=4$时，有下面合法队列：

FFFF、FFFM、MFFF、FFMM、MFFM、MMFF、MMMM

给定人数$n$求可能的合法队列数

  • 两种做法，一种分男女考虑合法与非法状况
  • 另一种设计子函数分别表示男女来生成

$\text{状态转移方程}\qquad F(n)=F(n-1)+F(n-2)+F(n-4)$

例六

有排成一行的$n$个方格，用R，P，G三色进行涂色，每格涂一种颜色，要求航信放个不能同色，首位两格也不能同色

  • 依旧是合法性分类

状态转移分析： - 前n-1格子序列合法的情况：$F(n-1)$ 此时第n个格子不能与合法的第一个和第n-1个颜色相同，只能有一种选择 - 前n-1格子序列非法的情况：$2F(n-2)$ 若想在第n个格子添加后生成合法的格子序列，该非法类型只能是第一个格子与第n-1个格子同色 这一部分的非法序列来源于合法的n-2序列添加一个首色格子，为$F(n-2)$ 此时的最后一个格子有两种颜色可以选择

故：$F(n)=F(n-1)+2F(n-2)$

例七

$2\times n$个数字按照顺时针方向围成一个圆，$n$条线段把所有数字两两相连，要求不能有交叉

求：有多少合法的连线方案

  • 卡特兰数列(Catalan)

1、2、5、14、642、132，……

$c[0]=1$

$c[n]=\sum_{i=0}^{n-1}c[i]c[n-1-i]$

$\Rightarrow c[n]=\frac{C_{2n}^{n}}{n+1}$

  • 高精度组合问题

第五讲 动态规划

典例1

![[Pasted image 20250225215005.png]] 有如上数塔，从顶部出发，在每一个节点都可以选择向左走或者向右走，一直走到底层，要求找到一条路径善意的路径上数值和最大

  • 首先考虑暴力求解，如何遍历所有路径，显然有$2^{n-1}$条路径，不予考虑
  • 分解子问题： 从顶点开始考虑左右两侧的最优解（类似二叉树考虑左右子树的最好情况） 时间复杂度：$O(n^2)$
  • 结论：自顶向下的分析，自底向上的计算

例一：免费馅饼

数轴上可能在某一时刻在某一位置掉落免费馅饼，0秒时人在5m处，每秒钟人只能移动一米，给出馅饼掉落的位置与时刻，给出获得馅饼最多的最优解

  • 显然问题仍然在于分解时间寻找最优解，问题是如何分解？
  • 注意到人的操作只有向左或向右或停止不动，那么将一维的数轴按照时间作为第二个轴进行绘图，发现其实就是数塔问题

典例二：最长有序子序列

I 0 1 2 3 4 5 6 7 8
Num[I] 1 4 7 2 5 8 3 6 9
  • 如何分解子问题？
  • 考虑到序列的寻找是从无至有的，也就是可以将问题规模从小到大考虑
I 0 1 2 3 4 5 6 7 8
Num[I] 1 4 7 2 5 8 3 6 9
F[I] 1 2 3 2 3 4 3 4 5

$F[I]$为以$Num[I]$为序列结束数字的最大长度，也就是将规模为n的问题分解为n个子问题分别计算，再进行比较即可

核心思想：利用已经解决的子问题作为已知条件进行演算后续问题（即：站在巨人的肩膀上看问题）

例二：胖老鼠问题

给出若干个老鼠的体重和速度，找到一个最长的序列，使得体重越来越大，速度越来越低

  • 按照体重递增排序，然后按照速度降序的原则寻找最长递减有序子序列

例三：最少拦截系统

给出n个飞弹，并且给出这n个飞弹的高度，有拦截系统进行拦截，且拦截系统拦截的多个导弹的高度只能递减

1：一套拦截系统最多可以拦截几个导弹？ 仍然是最长不递增有序子序列问题 2：最少需要几套拦截系统才能拦截所有导弹？

  • 尝试模拟？单次都做到拦截最多——贪心算法

  • 问题的本质：最少分成几个”最长不递增有序子序列问题“

    • Dilworth定理： 对于一个偏序集，最少链划分数等于最长反链长度
    • 结论：本体的本质为 求最长上升子序列的长度

例四：搬宿舍

搬宿舍，只能左手一个右手一个，搬东西消耗的能量为两者质量差的平方成正比。 已知有n个物品，需要搬k次，分别给出所有的物品重量，求消耗的最少能量

  • 第一感觉：两手的东西质量尽可能接近
  • 粗略思考验证：搬运一次必须要搬运质量相邻的两者
  • 预处理：排序
  • 问题的分解：搬运k次的最优解建立前k-1次的最优解情况，考虑递推，考虑dp
  • 设$F(n.k)$为在前n个物品中搬运k次，则可以分解问题

$F(n,1)=\min \begin{cases} (x_n-x_{n-1})^2\ F(n-1,1) \end{cases}$ - 如果拓展到$F(n,k)$呢？ 其实还是在分解问题，搬运第k次有两种，一种是这k次搬走了第n个物品，一种是没有，那么状态转移方程按照上述的思路即可解决：

$F(n,k)=\begin{cases} (x_n-x_{n-1})^2+F(n-2,k-1)\ F(n-1,k) \end{cases}$ - 注意问题的初始状态：问题规模在$F(4,2)$以下的都可以作为初始状态，$F(4,2)$的解显然为$(x_1-x_2)^2+(x_3-x_4)^2$

小结：

  • 基本思想：如果各个子问题不是独立的（即：重复的），不同的子问题的个数只是 多项式量级 （即：有限的），如果我们能用 数组 来保存已解决的子问题的答案，在需要时直接获取已求得的答案，这样就可以避免大量的重复计算
  • 特点：
    • 最优子结构 大问题的最优解一定包含子问题的最优解
    • 重叠子问题 子问题是重叠的，即大规模问题的解决牵扯到小规模问题
    • 无后效性 完成小规模问题后再完成大规模问题的时候，大规模问题的解决不会影响小规模的问题

第六讲 背包问题

导引问题

现有一张餐券面值10元，有菜肴N种，餐券一次性使用不可找零，问如何选择菜肴使得餐券使用最不浪费

什么是背包问题

  • 给定容量为$V$的背包和若干物品，在一定的限制条件下问最多能放进多少价值的物品
  • 最经典的DP问题
  • 背包问题中状态的理解（状态与状态转移）

背包问题分类

  • 01背包（非常重要！！！）
  • 完全背包
  • 多重背包
  • 二维费用背包
  • 混合三种背包
  • 分组背包
  • 有依赖的背包

01背包

  • 特点：每种物品仅有一个
  • 有$N$个物品和一个容量为$V$的背包，第$i$件物品的费用是$c[i]$，价值是$w[i]$，求解放入哪些物品使得价值总和最大
  • 问题特点：每种物品仅有一件，仅能选择放or不放
  • 子问题分解？ —— 基于状态
  • 无须→有序？ 从 $1$ 到 $i$ 依次考虑各个物品
  • 状态定义：$f[i][v]$表示考虑前$i$件物品后放入一个容量为$v$的背包可以获得的最大价值

例一

张三喜欢收集骨头，每个骨头有自己的价值和体积，求问背包可以装下最多价值的物品 例如：体积为10，有5块骨头，价值分别为1，2，3，4，5，体积分别为5，4，3，2，1

  • 仍然采取 第五讲例四 的思路
  • 从前0个物品依次考虑前 $i$ 个物品，按照这个顺序从背包体积为0到10依次进行分析
    1. 没装第$i$个物品——价值为$d[i-1][v]$（继承上一行的价值）
    2. 装第$n$个物品——此时的背包容量相比上一行能否放得下？如果放得下，放入并计算价值
  • 以上两个情况取 max 记录这个格子内
  • 得到了下面的表格（程序的执行过程即为从第一行到最后一行一次从左向右遍历
$(Y,C)$ 0 1 2 3 4 5 6 7 8 9 10
0 0 0 0 0 0 0 0 0 0 0 0
$(1,5)$ 0 0 0 0 0 1 1 1 1 1 1
$(2,4)$ 0 0 0 0 2 2 2 2 2 3 3
$(3,3)$ 0 0 0 3 3 3 3 5 5 5 5
$(4,2)$ 0 0 4 4 4 7 7 7 7 9 9
$(5,1)$ 0 5 5 9 9 9 12 12 12 12 14
  • 二维背包最能反映01背包的本质——考虑前1个，前2个，前3个……前i个，当背包体积最大时，得到的结果就是最优解
  • 状态转移方程：

$DP[i][j]=\max(DP[i-1][j],DP[i-1][j-v[i]]+w[i])$ - 时间复杂度与空间复杂度都为 $N \times V$ - 空间复杂度的优化：使用一维数组DP[j]，从后向前遍历 ```cpp for i = 1 to n for j = V to v[i] dp[j] = max(dp[j], dp[j-v[i]] + w[i])

## 完全背包 

- 特点：一种物品可以取无数个
- 可否转化为01背包？

## 多重背包
- 二进制优化
```cpp
//预处理
int t = 1;
while(x >= t) {
    v[cnt] = a * t;
    c[cnt++] = b * t;
    x -= t;
    t <<= 1; //按照2^k打包
}
if(x) {   //剩余打包
    v[cnt] = a * x;
    c[cnt++] = b * x;
}

二维费用背包

image.png

第七讲 BFS入门

  • 预备知识 队列 stl queue

层次遍历

  • 二叉树 image.png
  • 图

例

image.png

  • BFS标准套路 image.png

第八讲 DFS入门

导引 递归

  • 特征：
    • 先写出口（不需递归的特殊情况）
    • 再写普遍情况（递归解决）

例一 全排列

  • 递归特征：
  • 如果第一个数确定，则剩余问题就是其余 $n-1$ 个数字的全排列
  • 如果前 $k$ 个数确定，则剩余问题就是其余 $n-k$ 个数字的全排列
  • 枚举当前的每一种情况
    • 在每一种可能中，递归调用dfs(step + 1)
#include<bits/stdc++.h>
using namespace std;
int vis[10], num[10];
int n;

void dfs(int step) {
    if(step == n + 1) {
        for(int i = 1; i <= n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
    for(int i = 1; i <= n; i++) {
        if(vis[i] == 0) {
            num[step] = i;
            vis[i] = 1;
            dfs(step + 1);
            vis[i] = 0;  //回溯 
        }
    }
} 

int main() {
    while(cin >> n) {
        memset(vis, 0, sizeof(vis));
        dfs(1);
    }
    return 0;
}

例二 迷宫搜索

第八讲 二分匹配

  • 二分图 image.png

经典算法：匈牙利算法

变式一：最小定点覆盖

image.png