#创作计划# 基础算法笔记
2026-09-16 20:36:48
发布于：上海
点个赞评个论喵。
贪心
解决最值问题。
要求单步最值可以推出总体最值。
交换论证验证贪心策略：
在最优解中选择两个相邻元素交换，若结果不会更佳，则排序方式正确。
1.确定排序策略。
2.假设一种情况与排序方式不同。
不同方案例子： 在 的前面，且 。
将 位置互换，获得新方案 。
计算两者差距。
· 若 的结果不比 的差，说明贪心策略正确。
· 否则贪心策略是错误的。
举例说明：
交换前：前 个人是 ，后面每人要等 。
交换后：前 个人是 ，后面每人要等 。
交换更优，那么贪心策略是正确的。
一般适用于 的情况。
反悔贪心
普通：一旦做出选择永不回头。
反悔：带有限制的最优选取。
即可能在后期知道早期选择是错误的。
反悔贪心和 DP 的区别：
反悔贪心的前提是每个物品占用的空间是等价的，若不是等价的，则必须使用 DP 解决。
反悔贪心的实现：
1.按物品的某个维度排序。
2.维护小根堆，存已经选入方案的收益值。
3.考虑每个物品：
· 当前仍有空位：继续选，收益入堆。
· 没有空位：考虑当前收益是否大于堆顶，若是，反悔：弹出堆顶，将当前物品进堆。
二分
本质枚举，考虑好枚举对象和范围。
二分答案解决要求 最大值最小、最小值最大 的问题。
二分答案步骤：
1.确定二分对象。
2.确定改变区间的方式。
3.写 函数，使用其他算法判断能否做到。
二分答案的时间复杂度 函数时间复杂度 。
DP
线性DP
前 个满足题目条件的值。
一般来说题目需要哪些属性的描述就需要几维下标。
区间DP
状态设计：区间长度为 时，起点为 ，分割点为 时满足题目的属性。
树形/换根DP
状态设计：以 为根的子树满足的属性。
状压DP
状态设计：保存状态 时，满足条件的属性。
例题
[CSP-J 2022] 上升点列
状态设计：定义 为以 结尾且使用 个加点机会的最大值。
转移时枚举转移来源，此时需要 个额外点。
随后再枚举使用自由点的个数，暴力转移即可。
最后统计最大值。
#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
int n, k, dp[505][105];
pair <int, int> p[505];
int dist(int i, int j) {
return abs(p[i].x - p[j].x) + abs(p[i].y - p[j].y);
}
signed main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> p[i].x >> p[i].y;
sort(p + 1, p + n + 1);
for (int i = 1; i <= n; i++) dp[i][0] = 1;
for (int i = 1; i <= n; i++) for (int o = 1; o < i; o++) {
if (p[o].y > p[i].y) continue;
int need = dist(i, o) - 1;
for (int j = need; j <= k; j++) dp[i][j] = max(dp[i][j], dp[o][j - need] + need + 1);
} int maxn = 0;
for (int i = 1; i <= n; i++) for (int j = 0; j <= k; j++)
maxn = max(maxn, dp[i][j] + k - j);
cout << maxn;
return 0;
}
[CSP-J 2019] 纪念品
注意到可以进行 轮完全背包：
金币数为容量，今天价格为消耗，明日价格为价值。
#include <bits/stdc++.h>
using namespace std;
const int N = 105, M = 1000005;
int c[N][N], dp[M], t, n, m;
int main() {
cin >> t >> n >> m;
for (int i = 1; i <= t; i++) for (int j = 1; j <= n; j++) cin >> c[i][j];
for (int i = 1; i < t; i++) {
memset(dp, 0, sizeof dp);
for (int j = 1; j <= n; j++) {
int v = c[i][j], w = c[i + 1][j] - c[i][j];
for (int k = v; k <= m; k++) dp[k] = max(dp[k], dp[k - v] + w);
} m = max(dp[m] + m, m);
} cout << m;
return 0;
}
有趣的家庭菜园3
状态设计：前 盆花，最后一盆放第 号颜色的最小交换次数。
考虑到交换来源需要计算前面放了多少盆不同颜色的花，考虑使用 表示放了 盆红色， 盆绿色， 盆黄色。
最后摆放的是颜色 。
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n;
string s;
vector <int> p[3];
int sum[3][405];
int f[405][405][405][3];
// 计算跨越其他颜色时产生的逆序对
int get_cost(int c, int idx, int i, int j, int k) {
int pos = p[c][idx - 1];
int used[3] = {i, j, k};
int cost = 0;
for (int o = 0; o < 3; o++)
if (o != c) cost += max(0, used[o] - sum[o][pos]);
return cost;
}
int main() {
cin >> n >> s;
for (int i = 1; i <= n; i++) {
int c = (s[i - 1] == 'R' ? 0 : (s[i - 1] == 'G' ? 1 : 2));
p[c].push_back(i);
for (int j = 0; j < 3; j++) sum[j][i] = sum[j][i - 1];
sum[c][i]++;
} int c0 = p[0].size(), c1 = p[1].size(), c2 = p[2].size();
// 初始化
for (int i = 0; i <= c0; i++)
for (int j = 0; j <= c1; j++)
for (int k = 0; k <= c2; k++)
f[i][j][k][0] = f[i][j][k][1] = f[i][j][k][2] = INF;
f[0][0][0][0] = f[0][0][0][1] = f[0][0][0][2] = 0;
for (int i = 0; i <= c0; i++) for (int j = 0; j <= c1; j++)
for (int k = 0; k <= c2; k++) for (int lst = 0; lst < 3; lst++) {
int cur = f[i][j][k][lst];
if (cur >= INF) continue;
// 依次尝试
if (lst != 0 && i < c0) {
int cost = get_cost(0, i + 1, i, j, k);
f[i + 1][j][k][0] = min(f[i + 1][j][k][0], cur + cost);
}
if (lst != 1 && j < c1) {
int cost = get_cost(1, j + 1, i, j, k);
f[i][j + 1][k][1] = min(f[i][j + 1][k][1], cur + cost);
}
if (lst != 2 && k < c2) {
int cost = get_cost(2, k + 1, i, j, k);
f[i][j][k + 1][2] = min(f[i][j][k + 1][2], cur + cost);
}
}
int ans = min({f[c0][c1][c2][0], f[c0][c1][c2][1], f[c0][c1][c2][2]});
cout << (ans >= INF ? -1 : ans) << "\n";
return 0;
}
有帮助，赞一个