关于c++的几个简单算法

一. 动态规划（Dynamic Programming）

难点：状态转移方程的构建和初始化条件的设计
典型问题：01背包问题
分析：
状态定义 dp[i][j] 表示前i个物品放入容量为j的背包的最大价值。状态转移需要判断是否选择当前物品。

#include <iostream>
#include <algorithm>
using namespace std;int main() {int n, capacity;cin >> n >> capacity;int weight[n], value[n];int dp[n+1][capacity+1] = {0}; // 初始化为0for (int i = 0; i < n; i++) cin >> weight[i] >> value[i];for (int i = 1; i <= n; i++) {for (int j = 0; j <= capacity; j++) {if (j >= weight[i-1])  // 能装下当前物品dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i-1]] + value[i-1]);else dp[i][j] = dp[i-1][j]; // 不装当前物品}}cout << dp[n][capacity];return 0;
}

关键点：

• 状态转移方程：max(不选当前物品，选当前物品)

• 时间复杂度：O(n * capacity)，需注意数据规模是否允许。

1. 矩阵取数游戏（P1005）

• 题目类型：区间DP + 高精度

• 难点：需要处理大数运算（__int128或高精度类），状态转移涉及从两端取数的最优解。

• 状态定义：dp[i][j] 表示区间 [i, j] 取数的最大得分。

• 转移方程：

  dp[i][j] = max(dp[i+1][j] * 2 + a[i], dp[i][j-1] * 2 + a[j]);

• 代码参考：洛谷P1005题解。

---

2. 石子合并（P1880）

• 题目类型：区间DP + 环形处理

• 难点：环形问题需展开为链式（复制数组），并枚举分割点 k。

• 状态定义：dp[i][j] 表示合并区间 [i, j] 的最小/最大代价。

• 转移方程：

dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum[i][j]);

• 代码参考：洛谷区间DP题单。

---

3. 过河卒（P1002）

• 题目类型：坐标DP + 路径计数

• 难点：处理马的控制点（不可达位置），初始化边界条件。

• 状态定义：dp[i][j] 表示到达 (i, j) 的路径数。

• 转移方程：

  dp[i][j] = dp[i-1][j] + dp[i][j-1]; // 非马控制点

---

4. 滑雪（P1434）

• 题目类型：记忆化搜索（DFS + DP）

• 难点：需递归遍历四个方向，记忆化存储已计算的结果。

• 状态定义：dp[x][y] 表示从 (x, y) 出发的最长滑坡长度。

• 转移方程：

  dp[x][y] = max(dfs(nx, ny) + 1); // (nx, ny) 为合法邻接点

• 代码参考：动态规划与记忆化搜索题单。

---

5. 关路灯（P1220）

• 题目类型：区间DP + 状态附加维度

• 难点：需记录当前区间和位置（左/右端点），分类讨论移动方向。

• 状态定义：dp[i][j][0/1] 表示关闭 [i, j] 区间的灯后位于左/右端点的最小功耗。

• 转移方程：

  dp[i][j][0] = min(dp[i+1][j][0] + cost1, dp[i+1][j][1] + cost2);

• 代码参考：洛谷区间DP题单。

---

6. 合唱队形（P3205）

• 题目类型：区间DP + 双端插入

• 难点：需记录最后插入的元素是左端还是右端。

• 状态定义：dp[i][j][0/1] 表示区间 [i, j] 以左/右端结尾的排列方案数。

• 转移方程：

  if (a[i] < a[i+1]) dp[i][j][0] += dp[i+1][j][0];

• 代码参考：洛谷区间DP题单。

例题说明 ：

• 入门题：过河卒（P1002）、数字三角形（P1216）。

• 进阶题：石子合并（P1880）、关路灯（P1220）。

• 高难度题：矩阵取数（P1005）、滑雪（P1434）。

---

二. 图论 - 最短路径（Dijkstra算法）

难点：优先队列优化和松弛操作的理解
代码示例：

#include <vector>
#include <queue>
using namespace std;const int INF = 0x3f3f3f3f;
vector<pair<int, int>> graph[1001]; // 邻接表：graph[u] = {v, weight}
int dist[1001]; // 最短距离数组void dijkstra(int start) {priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;fill(dist, dist + 1001, INF);dist[start] = 0;pq.push({0, start});while (!pq.empty()) {int u = pq.top().second;int d = pq.top().first;pq.pop();if (d > dist[u]) continue; // 已找到更优路径，跳过for (auto &edge : graph[u]) {int v = edge.first, w = edge.second;if (dist[v] > dist[u] + w) { // 松弛操作dist[v] = dist[u] + w;pq.push({dist[v], v});}}}
}

关键点：

• 使用优先队列优化，每次取出距离最小的点。

• 松弛操作：若通过当前点u到达v更近，则更新dist[v]。

• 注意：Dijkstra不能处理负权边！

1. P4779 【模板】单源最短路径（标准版）

• 题目描述：给定有向图，求从源点出发到所有点的最短路径。

• 算法：Dijkstra堆优化（优先队列实现）。

• 关键点：

  • 使用邻接表存图。

  • 优先队列优化，时间复杂度为O((V+E)logV)。

  • 注意不能在更新时判断vis，而应在出队时判断。

• 代码参考：见洛谷P4779题解。

---

2. P3371 【模板】单源最短路径（弱化版）

• 题目描述：与P4779类似，但数据范围较小，适合练习基础Dijkstra。

• 算法：Dijkstra（未优化或优先队列优化）。

• 关键点：

  • 弱化版允许使用未优化的Dijkstra（O(V²)）。

  • 输出要求中，不可达点输出2³¹-158。

• 代码参考：见洛谷P3371题解。

---

3. P1339 Heat Wave G

• 题目描述：无向图，求从起点到终点的最短路。

• 算法：Dijkstra或SPFA（题目未禁用SPFA时）。

• 关键点：

  • 使用邻接矩阵存图（适合稠密图）。

  • 注意无向图的边需双向处理。

• 代码参考：见洛谷P1339题解。

---

4. P1629 邮递员送信

• 题目描述：求从源点到所有点的最短路及所有点返回源点的最短路之和。

• 算法：Dijkstra + 反向建图。

• 关键点：

  • 正向图跑一次Dijkstra，反向图再跑一次。

  • 反向图可将“返回路径”转化为单源最短路问题。

• 代码参考：见洛谷题单图论2-2。

---

5. P2296 寻找道路

• 题目描述：在满足路径点出边均与终点连通的条件下，求最短路径。

• 算法：拓扑排序 + Dijkstra/BFS。

• 关键点：

  • 先用反向图拓扑排序筛选合法点。

  • 再在合法点上跑最短路6。

• 代码参考：见洛谷P2296题解。

---

6. P1144 最短路计数

• 题目描述：求从起点到各点的最短路径条数（边权为1）。

• 算法：BFS或Dijkstra（带DP统计）。

• 关键点：

  • 若dis[y] == dis[x]+1，则累加路径数。

  • 需模100003输出4。

• 代码参考：见洛谷题单图论2-2。

---

题目编号	名称	算法	难度
P4779	单源最短路径（标准版）	Dijkstra堆优化	普及+/提高
P3371	单源最短路径（弱化版）	Dijkstra基础	普及-
P1339	Heat Wave G	Dijkstra/SPFA	普及
P1629	邮递员送信	Dijkstra + 反向图	普及+/提高
P2296	寻找道路	拓扑排序 + 最短路	提高+/省选-
P1144	最短路计数	BFS/Dijkstra + DP	普及+/提高

例题说明： 建议按顺序练习，从模板题（P3371、P4779）开始，逐步挑战综合应用题（如P2296）。更多题目可参考洛谷题单图论2-2。

---

三. 深度优先搜索（DFS）与剪枝

难点：剪枝条件的合理设计
典型问题：全排列问题
代码示例：

#include <iostream>
using namespace std;int n, path[10];
bool visited[10];void dfs(int step) {if (step == n) { // 终止条件for (int i = 0; i < n; i++) cout << path[i] << " ";cout << endl;return;}for (int i = 1; i <= n; i++) {if (!visited[i]) { // 剪枝：已用过的数字不再选visited[i] = true;path[step] = i;dfs(step + 1);visited[i] = false; // 回溯}}
}int main() {cin >> n;dfs(0);return 0;
}

关键点：

• 使用visited数组避免重复选择，实现剪枝。

• 回溯时恢复状态（visited[i] = false）。

---

四. 并查集（Union-Find）

难点：路径压缩和按秩合并的优化
代码示例：

int parent[1001];
int rank[1001];void init() {for (int i = 0; i < 1001; i++) {parent[i] = i;rank[i] = 1;}
}int find(int x) { // 路径压缩if (parent[x] != x)parent[x] = find(parent[x]);return parent[x];
}void union_set(int x, int y) { // 按秩合并int rootx = find(x), rooty = find(y);if (rootx == rooty) return;if (rank[rootx] > rank[rooty]) parent[rooty] = rootx;else {parent[rootx] = rooty;if (rank[rootx] == rank[rooty]) rank[rooty]++;}
}

关键点：

• find函数通过递归实现路径压缩，降低树高。

• union_set根据秩的大小合并，避免树退化。

---

五. 贪心算法（Greedy）

难点：正确性证明和贪心策略的选择
典型问题：区间调度（选择最多不重叠区间）
代码示例：

#include <vector>
#include <algorithm>
using namespace std;struct Interval {int start, end;
};bool compare(Interval &a, Interval &b) {return a.end < b.end; // 按结束时间排序
}int maxIntervals(vector<Interval> intervals) {sort(intervals.begin(), intervals.end(), compare);int count = 0, last_end = -1;for (auto &itv : intervals) {if (itv.start >= last_end) {count++;last_end = itv.end;}}return count;
}

关键点：

• 贪心策略：优先选择结束时间早的区间。

• 正确性证明：局部最优（选最早结束）导致全局最优。

---

总结

1. 动态规划：从简单模型（如背包）入手，理解状态定义。

2. 图论：熟练Dijkstra和Floyd算法的应用场景。

3. 搜索：合理剪枝，避免暴力超时。

4. 并查集：必须掌握路径压缩优化。

5. 贪心：多练习经典问题，如区间问题、哈夫曼编码等。