作业介绍
AF
- 选手： 位置， 国籍
- 找到不同国籍的最近的那个人的和自己的距离
- 左边最近和右边最近， min(左边 ， 右边)
- 左边最近 f1[i] : 与 i 位置不同国籍的人的距离，
- 上一个就是不同的 ，a[i].x - a[i-1].x
- 上一个国籍和当前相同， f1[i-1] + a[i].x - a[i-1].x
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5+10;
int n, dp_l[N], dp_r[N];
struct node {
int c, x, id1, id2;
} a[N];
bool cmp1(node a, node b) {
return a.x < b.x;
}
bool cmp2(node a, node b) {
return a.id1 < b.id1;
}
signed main(void) {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].c >> a[i].x, a[i].id1 = i;
}
sort(a + 1, a + n + 1, cmp1);
for (int i = 1; i <= n; i++) a[i].id2 = i;
memset(dp_l, 0x3f, sizeof dp_l);
for (int i = 2; i <= n; i++) {
if (a[i].c != a[i - 1].c) dp_l[i] = min(dp_l[i], a[i].x - a[i - 1].x);
else dp_l[i] = min(dp_l[i], dp_l[i - 1] + a[i].x - a[i - 1].x);
}
memset(dp_r, 0x3f, sizeof(dp_r));
for (int i = n - 1; i >= 1; i--) {
if (a[i].c != a[i + 1].c) dp_r[i] = min(dp_r[i], a[i + 1].x - a[i].x);
else dp_r[i] = min(dp_r[i], dp_r[i + 1] + a[i + 1].x - a[i].x);
}
sort(a + 1, a + n + 1, cmp2);
for (int i = 1; i <= n; i++) {
cout << min(dp_l[a[i].id2], dp_r[a[i].id2]) << '\n';
}
return 0;
}
AG
-
和固定， 求乘积最大， 两个数差最小
-
对于每个物品，就是选或者不选， 容量应该是 sum/2
-
求 1 - sum/2 之间能凑出的最大的数是多少，maxx
-
01 背包
-
f[0] =1 , f[j] = f[j] |f[j-a[i]]
-
res = maxx * (sum - maxx)
-
二进制枚举
-
每一个位置要么选，要么不选，
AF
- f[i] : 到 i 位置结束的时候，能选择的子序列的个数
- i 位置能选的前提是， 这个位置要能在序列里面
- f[i] 不选： f[i-1] 选择：f[i-2] + 1 , 取 max
AI
- f[i] 调到 i 位置的最少跳跃次数
- i 可以从哪些地方跳到 ， f[i] = min(f[j] + 1)(1<=j<i) , (a[i]-a[j]<=跳跃距离)
- 最后的落脚点是 l 位置， a[n+1] = l,
AJ
- n 个不同的糖果 , k 个盒子， 放置的方案数
- f[i][j] i 个糖果, j 个盒子的放置方案
- f[i][j] : 对于第 i 个糖果， 1. 重新来一个盒子： f[i-1][j-1]
-
- 放在之前的盒子里面： (i-1)*f[i-1][j]
-
- 注意取模
AK
- 减 a 减 b 小于等于 c
- +a ,+b 等于 n 的方案数
- 基数：0 1 2 3 ... c f[基数] =1
AL
- 凑出 2， 有2 就行 f[2]++
- 凑出 20 ， 当前是 0 ， f[20] += f[2]
- 凑出 202， 当前是 2 ，f[202] += f[20] , f[2]++
- 凑出2023， 当前是 3， f[2023] += f[202]
R
- 01背包
- f[j] = max(f[j] , f[j-v[i]]+v[i]);
S
- f[i] :打 i 个字需要的最小次数
- f[i] = (f[i-1]+1, f[i/2]+1 (i是偶数))
- f[1] = 1
T
- f[i][j] 到 i 和 j 的最小花费
- f[i][j] = min(f[i-1][j], f[i-1][j-1], f[i-1][j+1]) + a[i][j];
- a[i][j] = ((i-1)*c+j) % 5
- 20000*20000 的数组，开不出来，滚动数组
#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10;
int r, c, m;
int f[2][N];
int main() {
cin >> r >> c >> m;
memset(f, 0x3f, sizeof f);
for (int i = 1; i <= c; i++)
f[0][i] = 0;
// 备份一个临时数组
for (int i = 1 ; i <= r; i++) {
for (int j = 1; j <= c; j++) {
int tmp = ((i - 1) * c + j) % m;
if (tmp == 0)
tmp = m;
f[i & 1][j] = tmp + min(f[(i - 1) & 1][j], min(f[(i - 1) & 1][j - 1], f[(i - 1) & 1][j + 1]));
}
}
int res = 0x3f3f3f3f;
for (int i = 1; i <= c; i++)
res = min(f[r & 1][i], res);
cout << res;
return 0;
}
U
- 完全背包
- n 个人分成若干小组，求积极度最大值
- 每个小组， 人数 i (w[i] = i), 积极度 a[i] (v[i] = a[i])
- 总容量 ：n
- 每个人一个组别： n 个组
V
- f[i] : 到 i 位置的最少移动步数
- f[i] = min(f[i-1]+1 ， f[i-2]+1)
- 障碍物，障碍物地的值，设置为 无穷大，
W
- 完全背包
- w[i] = pow(i,4), v[i] = 1
X
- 01背包
Y
- 求从某个点出发，恰好移动 k 步之后，到达的点可能有哪些
- 状态： 出发的点，花费多少步数，
- f[t][i][j] : 从 i 出发 走 t 步 是否能到达 j ， 0 或者 1
- res = sum(f[k][i][j] == 1 )
- 转移： 类似：BFS ， pair<u , t > , pair<to[u] , t+1>
- f[t][i][to[j]] |= f[t-1][i][j] +1
Z
- 最长上升子序列 f[i] : 以 a[i] 结尾最长上升子序列的长度
- 多了：相邻树的间隔相同（所处的坐标之间的间隔）
- f[i][j] : 以 a[i]结尾间隔为 j 的最长上升子序列的长度
- f[i][j] = max(1, f[i-j][j]+1) (a[i] >a[i-j])
AA
- f[i] :以 a[i]结尾的最大价值和
- f[i] = max(f[i-1] , f[i-2]+s[i]-'a'+1)
AB
- 最大字段和
- f[i] = max(0, f[i-1]) +a[i];
- memset(f, 0xcf, sizeof f); // 赋值为极小值
AC
- 最大字段和 maxx
- res = sum + maxx*(k-1)
AD
- 对于加减后的结果大于 360 的，值需要对 360 取模
- f[j] : 角度为 j 的能否凑出
- f[j] : f[j%360] |= f[(j-a[i])%360]
- f[j] : f[j%360] |= f[(j+a[i])%360]
AE
- 砝码：不放， 放左边，放右边
- f[i][j] : 前 i个砝码能否凑出 j ，
- f[i][j] 1. w[i]==j , f[i][j] =1;
-
2. f[i][j] |= f[i-1][j+w[i]] -
3. f[i][j] |= f[i-1][abs(j-w[i])] -
4. f[i][j] |= f[i-1][j] 不放 - res = sum(f[n][i] == 1)
01 背包
// 二维 01 背包
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int w[N], v[N];
int f[N][N];
int n, m;
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i++)
cin >> w[i] >> v[i];
for (int i = 1; i <= n; i++) {
for (int j = 1 ; j <= m; j++) {
f[i][j] = f[i - 1][j]; // 不放当前物品
if (j >= w[i])
f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);
}
}
cout << f[n][m];
return 0;
}
- 一个维度： f[j] : 在容量为 j 的情况下的最大价值
- 转移方程：f[j] = max(f[j] , f[j-w[i]]+v[i]);
// 二维 01 背包
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int w[N], v[N];
int f[N];
int n, m;
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i++)
cin >> w[i] >> v[i];
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]);
cout << f[m];
return 0;
}
完全背包
- 一个维度： f[j] : 在容量为 j 的情况下的最大价值
- 转移方程： f[j] = max(f[j] , f[j-w[i]]+v[i]);
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10;
int w[N], v[N];
long long f[N];
int n, m;
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i++)
cin >> w[i] >> v[i];
for (int i = 1; i <= n; i++)
for (int j = w[i] ; j <= m; j++)
f[j] = max(f[j], f[j - w[i]] + v[i]);
cout << f[m];
return 0;
}
- 完全背包
- 组合方案数， 排列方案数
- 组合： 先遍历物品，再遍历容量：(先遍历物品，保证了物品只会按照顺序出现)
- 排列： 先遍历容量，再遍历物品：(后遍历物品，无法保证物品按照顺序出现，排列)
多重背包
- 枚举顺序： 物品 - 数量 - 容量 物品 - 容量 - 数量
#include <bits/stdc++.h>
using namespace std;
const int N = 4e4 + 10;
int w[N], v[N], c[N];
long long f[N];
int n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i] >> c[i];
// O(n*m*k)
for (int i = 1; i <= n; i++)
for (int k = 1; k <= c[i]; k++)
for (int j = m; j >= 1; j--)
if (j - w[i] >= 0)
f[j] = max(f[j], f[j - w[i]] + v[i]);
cout << f[m];
return 0;
}
- 二进制优化： 1 - 10 之间的数字可以用 1 2 4 3 每个数字至多用一次表示出来
- 通过二进制优化转化成 01 背包
- 二进制优化以后，物品的数量会变成：n*log2(k)
#include <bits/stdc++.h>
using namespace std;
const int N = 4e4 + 10;
int w[N], v[N], tot;
long long f[N];
int n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int a, b, c;
cin >> a >> b >> c; // v w c
// 二进制优化
for (int j = 1; j <= c; j *= 2) {
// c 可以拆出一个 j
// 相当于 j 个物品凑成一组
w[++tot] = b * j;
v[tot] = a * j;
c -= j; // 拆出了j
}
// 拆完以后可能有剩余
if (c) { // c 个物品凑成一组
w[++tot] = b * c;
v[tot] = a * c;
}
}
// 01 背包
for (int i = 1 ; i <= tot; i++)
for (int j = m; j >= w[i] ; j--)
f[j] = max(f[j], f[j - w[i]] + v[i]);
cout << f[m];
return 0;
}
//10 1 - 10
//1 2 4 3 1-10 之间的数字可以用 1 2 4 3 表示出来
//1 2 3 4 5 6 7 8 9 10
混合背包
- 01背包， 完全背包 ，多重背包
- 多重二进制优化成01背包
- 剩下 01和完全，分类讨论，如果是01 倒着循环容量， 完全正着循环容量
for (int i = 1; i <= tot; i++)
if (vis[i]) // 标记数组，标记是 完全背包
for (int j = t[i]; j <= T; j++)
f[j] = max(f[j], f[j - t[i]] + c[i]);
else
for (int j = T; j >= t[i]; j--)
f[j] = max(f[j], f[j - t[i]] + c[i]);
二维费用背包
- 状态： f[j][v] 在重量为 J ,题解为 v 的情况下的最大价值，
- 转移方程： f[j][v] = max(f[j][v] , f[j-w[i]][v-V[i]] +value[i]);
#include <bits/stdc++.h>
using namespace std;
const int N = 410;
int n, H, T;
int h[N], t[N], k[N];
int f[N][N];
int main() {
cin >> H >> T;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> h[i] >> t[i] >> k[i];
for (int i = 1; i <= n; i++)
for (int j = H; j >= h[i] ; j--)
for (int l = T ; l >= t[i] ; l--)
f[j][l] = max(f[j][l], f[j - h[i]][l - t[i]] + k[i]);
cout << f[H][T];
return 0;
}
分组背包
- f[j] : 容量为 j 的最大价值
- f[j] = max(f[j] , f[j-w[i]]+v[i])
- 遍历顺序： 组别 - 容量 - 组里面的元素
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n, m;
int w[N], v[N];
int f[N];
vector<int> a[N];
int maxx; // 最大组别数
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> w[i] >> v[i] >> x;
a[x].push_back(i); // 第 i个物品属于 x 组别
maxx = max(maxx, x);
}
for (int i = 1; i <= maxx; i++) // 组别
for (int j = m; j >= 1; j--) { // 容量
for (auto k : a[i]) {
if (j >= w[k])
f[j] = max(f[j], f[j - w[k]] + v[k]);
}
}
cout << f[m];
return 0;
}
有依赖的背包
- 分主件和附件， 附件依赖于主件
- 主件和附件组合的可能 ： 1. 主件 2. 主件+附件1 3.主件+附件2
-
- 主件 + 附件1 + 附件2
// 给定钱的总数，求价格和重要度的乘积的最大值
// 主件和附件， 附件只有在买了主件的前提下才能买
// 1. 主件 2. 主件+附件1 3.主件+附件2
// 4. 主件 + 附件1 + 附件2
#include <bits/stdc++.h>
using namespace std;
const int N = 32010;
int v[N], p[N];
int f[N];
int n, m;
bool vis[N]; // vis[i] = 1 , i 是主件
vector<int> a[N]; // 记录某个主件的附件的编号
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x;
cin >> v[i] >> p[i] >> x;
if (x == 0)
vis[i] = 1;
else
a[x].push_back(i); // 第 i 个属于主件 x 的附件
}
for (int i = 1; i <= n; i++) {
if (vis[i] == 0)
continue;
for (int j = n; j >= 1; j--) {
// 主件
if (j >= v[i])
f[j] = max(f[j], f[j - v[i]] + v[i] * p[i]);
// 主件 +附件1
if (a[i].size() > 0) {
if (j >= v[i] + v[a[i][0]])
f[j] = max(f[j], f[j - v[i] - v[a[i][0]]] + v[i] * p[i] + v[a[i][0]] * p[a[i][0]]);
}
// 主件 + 附件 2
if (a[i].size() > 1) {
if (j >= v[i] + v[a[i][1]])
f[j] = max(f[j], f[j - v[i] - v[a[i][1]]] + v[i] * p[i] + v[a[i][1]] * p[a[i][1]]);
}
// 主件+附件1 + 附件2
if (a[i].size() > 1) {
if (j >= v[i] + v[a[i][1]] + v[a[i][0]])
f[j] = max(f[j], f[j - v[i] - v[a[i][1]] - v[a[i][0]]] + v[i] * p[i] + v[a[i][1]] * p[a[i][1]] + v[a[i][0]] *
p[a[i][0]]);
}
}
}
cout << f[n];
return 0;
}
背包方案数
- 状态； f[j] : 凑出 j 的方案数量
- 转移方程：f[j] += f[j-w[i]] , f[0] =1;
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
const int M = 1e4 + 10;
int n, m, a[N];
int f[M];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
f[0] = 1;
for (int i = 1; i <= n; i++)
for (int j = m; j >= a[i] ; j--)
f[j] += f[j - a[i]];
cout << f[m];
return 0;
}
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]
-
- 遍历之前所有发放时间比 当前时间早的 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 价值：价格 +运费， 数量：每个商店有几吨
题目
- 状态
- 已结束
- 题目
- 46
- 开始时间
- 2026-4-12 0:00
- 截止时间
- 2026-5-31 23:59
- 可延期
- 24 小时