#创作计划#XP03AD1~2笔记
2026-07-23 20:17:08
发布于：浙江
8阅读
0回复
0点赞
D1:DFS的复习
1.01枚举(01背包削弱版)
void dfs(int now){ // 层数
if (now == n + 1){
// TODO sth 做某事
return;
}
b[now] = 1; // b指选择此数
dfs(now + 1); // 递归
b[now] = 0;
dfs(now + 1);
}
2.排列枚举
void dfs(int now){
if (now == n + 1){
// TODO sth
return;
}
for (int i = 1;i <= 10;i++){
b[now] = i;
dfs(now + 1);
}
}
D2:BFS的复习
真神模板
void bfs(int start, int end){ //开头与终点
memset(dist, -1, sizeof dist);
queue<int>q;
q.push(start);
while(q.size()){
int t = q.front();
q.pop();
if (end == t)break; //遇到终点直接结束
for(邻居v){
if (邻居v判断){
dist[v] = dist[t] + 1;
q.push(v);
}
}
}
}
D3:DP复习
DP最难的点在于没有模板，以下是DP四要素:
1.DP[i]表示的状态
2.初始化
3.状态转移方程(式)
4.输出
简单例题
最长上升子序列:
#include<bits/stdc++.h>
using namespace std;
struct spaceline{int x, y;}a[1001];
bool rcmp(spaceline X, spaceline Y){
return X.x < Y.x;
}
int dp[1001];
signed main(){
int n; cin >> n;
for (int i = 1;i <= n;i++){
cin >> a[i].x >> a[i].y;
}
sort (a + 1, a + n + 1, rcmp);
for (int i = 1;i <= n;i++) dp[i] = 1;
for (int i = 2;i <= n;i++){
for (int j = 1;j < i;j++){
if (a[i].y < a[j].y)dp[i] = max(dp[i], dp[j] + 1);
}
}cout << *max_element(dp + 1, dp + n + 1);
return 0;
}
最长公共子序列
#include <bits/stdc++.h>
using namespace std;
string a, b;
int n, m, dp[1001][1001];
signed main(){
cin >> a >> b;
n = a.size();
m = b.size();
a = ' ' + a;
b = ' ' + b;
for (int i = 1;i <= n;i++){
for (int j = 1;j <= m;j++){
if (a[i] == b[j])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}cout << dp[n][m];
}
这里空空如也
有帮助，赞一个