A

• f[i]: 到 i 为止的最大和，必须包含 a[i]
• 转移方程：1. 只有 a[i] 一个 2. a[i]连上之前的某一段
• f[i] = max(a[i] , f[i-1]+a[i]);
• 注意：值可以为负数，

B

• f[i] : 走到i的时候的最多能获得的礼物，保证 i 是一定要拿到的, 这个时候的时间一定是 a[i]
• 拿到礼物 i 的时间a[i]， 之前拿的礼物发放时间肯定在 a[i] 前面，
• 对礼物的发放时间进行排序，依次来，
• 转移：1. 自己一个 1 ， 2. 在之前拿完某个以后到 a[i]
• 2. 遍历之前所有发放时间比 当前时间早的 j， 满足条件： a[j] + t[j][i] <= a[i]
• 注意点：struct node{int t, id; // id 摊位号}

c

• f[i] : 到达 i 的最大分数
• i 可以是通过 任意一个通道 a[j] 到达 ， f[i-a[j]] + b[i - a[j]]

D

• f[i] :到达 i 的方案数
• 斐波那契一样的， f[i] = f[i-1]+f[i-2]+f[i-3]

E

• 完全背包
• 组合方案数， 排列方案数
• 组合： 先遍历物品，再遍历容量：(先遍历物品，保证了物品只会按照顺序出现)
• 排列： 先遍历容量，再遍历物品：(后遍历物品，无法保证物品按照顺序出现，排列)

F

• 完全背包
• 物品重量 w[i] = i*i , 价值 v[i] = 1
• min , 初始值，正无穷， f[0] =0;

G

• 河中心只有 0 个石墩：m 个荷叶：最多能有多少青蛙：m+1
• 状态： f[i] : 河中心有 i 个石墩的时候，能有的青蛙的数量
• f[0] = m+1
• f[1] = f[0] + m+1 = 2*m + 2
• f[2] = f[0] +f[1] + m+1
• f[i] = f[0] +f[1] +...f[i-1] + m+1

H

• 状态：到 i 的最多组数
• 转移： 1. f[i]=1, (a[i]>=0) , 自己单独一组 2.f[i] = f[j] +1 和之前的部分形成一段(1- j之间 , j+1 - i 之间是新的一段)(sum[i] - sum[j]>=0)

I

• 题目分类， 每个类别里面选无数个
• 完全背包：题目花费的时间就是重量， 题目的分数就是价值

J

• 合法队列：112222 111112 12 11 22
• 题目要求就是:把不合法队列修改成合法队列的最小次数
• 状态：f[i][j] 到 i 为止状态为 j 合法的最小次数， (i位置是 1 ，是 2 两种可能)
• 转移：f[i][1] = f[i-1][1] + (a[i]!=1) , i 位置是1，之前的所有位置都得是 1
• 转移： f[i][2] = min(f[i-1][1] , f[i-1][2]) + (a[i] != 2)
• 输出 min(f[n][1] , f[n][2])

K 多重背包

• // 多重背包的基础是 01 背包？
• // 01 背包 倒着循环容量保证了只取一个 // 01 背包 for (int i = 1; i <= n; i++) // 遍历物品 for (int j = m; j >= w[i]; j--) // 遍历容量 f[j] = max(f[j], f[j - w[i]] + v[i]);

// 多重背包 for (int i = 1; i <= n; i++) // 遍历物品 for (int k = 1 ; k <= c[i]; k++) // 遍历数量 for (int j = m; j >= w[i]; j--) // 遍历容量 f[j] = max(f[j], f[j - w[i]] + v[i]);

• 优化：二进制优化
• for (int i = 1; i <= n; i++) { int a, b, c; cin >> a >> b >> c; // 二进制拆分 for (int j = 1 ; j <= c; j *= 2) { // 拆分出 j 件 w[++tot] = a * j; v[tot] = b * j; c -= j; } if (c) { w[++tot] = c * a; v[tot] = c * b; } }

L

• 完全背包

M

• 完全背包， 求最小值，初始化为最大值
• f[0] = 0;
• f[j] = min(f[j] , f[j-w[i]]+1)

N

• 一个人只能说固定的单词
• 判断某一句话，他能不能说 ， 判断某一句话能不能凑出来
• 状态：f[i] 第 i 位能不能匹配
• 转移：1. 存在第 i 位置这个单词， f[i] =1

•  2.  存在第 i 位和 i+1 位置合起来的单词， f[i+1] =1 
  

• unordered_set

O

• 01背包，限制了重量和体积
• f[i][j] = max(f[i][j] , f[i-w[i]][j-v[i]]+value[i])

P

• 层级， 点的编号
• f[i][j] : 到达第 i 层， 第 j 个点的最小花费
• f[0][1] = 0 ， 初始化为极大值
• f[i][j] = min(f[i][j] , f[i-1][能到达 j的点] +当前航线的花费)
• 无需建图，直接边输入边处理

Q

• 买饲料的花费：本身的价格 + 运费， 分别算出每一吨花费多少钱
• 买 K 吨， 容量
• 贪心： 优先购买每一吨花费最小的饲料
• 多重背包： 重量： 每吨是1 价值：价格 +运费， 数量：每个商店有几吨