非常坐牢的dp，几乎每题都使用了ai才能做出来。由于还没系统上过y总的课，而且据说y总的课要细品而不能速通。故只能硬着头皮在chatgpt以及哔哩哔哩上的各个视频的帮助下硬着头皮做下去。感觉这篇文章的工程量会非常的大，而且会很长。
题目来源：
2026年USST蓝桥杯软件类市赛训练-1-DP经典题
A-D dp入门题
A-D题是算比较简单的dp题目，基本跟着题目描述自己一步一步慢慢推能想出来，也是少数没有借助AI而直接做出来的题目，同时不能算是模板题，普适性比较低，故这里不做题解。
E-H 背包问题
背包问题是一类非常经典的dp问题，这里有几个模板。在背包问题中要谨防爆long long!
E 01背包-1
Problem Statement
There are N items, numbered 1,2,…,N. For each i (1≤i≤N), Item i has a weight of w_i and a value of v_i .Taro has decided to choose some of the N items and carry them home in a knapsack. The capacity of the knapsack is W, which means that the sum of the weights of items taken must be at most W.
Find the maximum possible sum of the values of items that Taro takes home.
Constraints
All values in input are integers.
1≤N≤100
1≤W≤1e5
1≤wi≤W
1≤vi≤1e9 二维dp
非常经典的01背包，b站上有大佬通过视频动画生动形象地解释了经典01背包的原理，视频如下：
总而言之，经典的01背包就开一个二维的dp数组，行代表当前是第 i 个物品，列代表当前的最大容积为 j
那么对于dp[i][j]，可能会由两种状态被更新过来
一种情况是当前的容量小于第 i 个物品需要的容量，也就是说，第i个物品目前放不下。那么在这种情况下，取前 i 个物品能够获得的最大价值和取前 i – 1 个物品能够获得的最大价值是完全一样的，因为第 i 个物品没有被放进背包中。而对应的数组的状态更新就意味着dp[i][j]由dp[i – 1][j]更新过来。
另一种情况是当前的背包放得下第 i 个物品。那么我们需要比较两个东西：拿第 i 个物品和不拿第 i 个物品，哪个价值更大一点。不拿第 i 个物品的价值我们已经知道是 dp[i – 1][j] 了，那么拿第 i 个物品呢？该如何计算？
由于我们已经拿了第 i 个物品， 所以肯定有了 v[i] 的价值。这个时候我们就要考虑在我们的背包已经放进去了第 i 个物品的情况下，在前 i – 1 个物品中最大能获得多少的价值。显然，第 i 个物品占用了 w[i] 的空间，所以我们的背包剩下的容量就是 j – w[i]，那么我们此时我们获得的最大的价值就是 v[i] + dp[i – 1][j – w[i]]了。
核心的dp代码如下
void solve()
{
int n, W; cin >> n >> W;
vector<int> w(n + 1), v(n + 1);
vector dp(n + 1, vector<int>(W + 1));
for (int i = 1; i <= n; i ++ ) cin >> w[i] >> v[i];
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= W; j ++ )
{
if (j < w[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]]);
}
}
cout << dp[n][W] << '\n';
return ;
}一维滚动
二维的dp非常便于理解，逻辑很清楚，但是当数据量比较大的时候，容易出现一个致命的缺陷：MLE！那我们就要想办法降低数据存储量了。
我们通过观察可以发现，我们每次第 i 行的dp都是由第 i – 1 行更新过来的，也就是说，我们并没有必要去保存第 1 行到第 i – 2 行的东西，只要我们对于每一个 i 在遍历时，直接更新成最新的数据就可以了，这样我们就省掉了一个维度，省下了大量的空间。
但是，我们要注意一点，我们更新状态的时候取到了第 j – w[i] 列的值，也就是说，如果我们从 1 到 W 遍历，会出现一个问题：我们在滚动的数组中取到的dp[j – w[i]]不是dp[i – 1][j – w[i]] 而是 dp[i][j – w[i]]，因为我们在 j 取 j – w[i] 时已经更新过一遍了，所以我们必须倒着遍历，来实现一维滚动数组的dp
注意j >= w[i]防止数组越界，以及取max
代码如下：
void solve()
{
int n, W; cin >> n >> W;
vector<int> w(n + 1), v(n + 1);
vector<int> dp(W + 1);
for (int i = 1; i <= n; i ++ ) cin >> w[i] >> v[i];
for (int i = 1; i <= n; i ++ )
{
for (int j = W; j >= w[i]; j -- )
{
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout << dp[W] << '\n';
return ;
}F 01背包-2
一样的问题，但是数据范围变了。v的总和的最大值小于10000，但是总容量非常大(1e9)。这时我们就不能直接用刚刚的方法dp了，肯定会TLE的。这时经过AI的提示，我们发现要对价值进行dp。也就是说，
有了这个思想以后，我们就可以手搓dp了。因为要找最小的重量，所以我们默认使用无穷大，这里采用LONG_LONG_MAX进行初始化。那接下来的情况和经典01背包相似，也分两种情况考虑：拿第 i 个物品和不拿第 i 个物品
先看不拿第 i 个物品的情况。
不拿第 i 个物品时，要达到 j 的价值，最少需要dp[i – 1][j]的重量。先不管是否可能达到，直接继承。
然后看拿第 i 个物品的情况。
拿了第 i 个物品以后，我们就需要知道，在第1~n – 1个物品中，达到 j – v[i] 的价值需要多少重量。也就是说在拿了第 i 个物品时，到达价值 j 所需的重量为 w[i] + dp[i – 1][j – v[i]]。
然后记得在循环中取最小值，最后还要看一下，在dp[n][j] <= W的情况下，j 的最大值是多少。说人话就是看一下，在第1 ~ n 个物品中，拿的重量小于规定重量的情况下，v的价值是多少。
代码如下：
vector dp(n + 1, vector<ll>(vm + 1, INF));
dp[0][0] = 0;
for (int i = 1; i <= n; i ++ )
{
for (int j = 0; j <= vm; j ++ )
{
dp[i][j] = dp[i - 1][j];
if (j >= v[i] && dp[i - 1][j - v[i]] != INF)
dp[i][j] = min(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
}
}
int ans = 0;
for (int j = 0; j <= vm; j ++ )
{
if (dp[n][j] <= W) ans = j;
}在原题中，二维的dp也能开得下。但是可以优化空间到一维dp。总结过程和上面一样，这里直接给代码
vector dp(n + 1, vector<ll>(vm + 1, INF));
dp[0][0] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = vm; j >= v[i]; j--)
{
if (dp[j - v[i]] != INF)
dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
}
};G 完全背包
完全背包的代码与01背包几乎一样，不同之处在于如果二维那么就dp[i – 1][j]改成dp[i][j]，如果一维那么直接正着遍历。因为一个物品可以取无穷次，所以我们在考虑取了第 i 个物品后，还能继续取第 i 个物品，而不是像01背包那样只能在前 i – 1 个里面选。所以状态转移方程里面的v[i] + dp[i – 1][j – t[i]]就变成了v[i] + dp[i – 1][j – t[i]]相应地，在一维dp中，只要正序遍历即可。
二维dp
void solve()
{
int n, W; cin >> n >> W;
vector<int> w(n + 1), v(n + 1);
vector dp(n + 1, vector<int>(W + 1));
for (int i = 1; i <= n; i ++ ) cin >> w[i] >> v[i];
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= W; j ++ )
{
if (j < w[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], v[i] + dp[i][j - w[i]]);
}
}
cout << dp[n][W] << '\n';
return ;
}一维dp
void solve()
{
int T, M; cin >> T >> M;
vector<ll> t(M + 1), v(M + 1);
for (int i = 1; i <= M; i ++ )
cin >> t[i] >> v[i];
vector<ll> dp(T + 1);
for (int i = 1; i <= M; i ++ )
{
for (int j = t[i]; j <= T; j ++ )
{
dp[j] = max(dp[j], dp[j - t[i]] + v[i]);
}
}
cout << dp[T] << '\n';
return ;
}H 理解背包正确性
据说是一道很难的题目。这里直接贴大佬的题解
第十一届中国大学生程序设计竞赛 哈尔滨站（CCPC 2025 Harbin Site） – 空気力学の詩 – 博客园
I 最长公共子序列 （LCS）
You are given strings s and t. Find one longest string that is a subsequence of both
s and t.做的时候借助gpt完成，现在写文章的时候又忘了思路，但在bilibili上找到了不错的视频，可以求出最长公共子序列，讲得非常详细。
于是，我放弃了自己解释，并且贴出了代码
void solve()
{
string s, t; cin >> s >> t;
int n = s.size(), m = t.size();
vector dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++ )
{
if (s[i - 1] == t[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
// 开始回溯
int i = n, j = m;
string ans = "";
while (i > 0 && j > 0)
{
if (s[i - 1] == t[j - 1]) // 当前相等，回溯到左上角
{
ans += s[i - 1];
i -- ;
j -- ;
}
// 回溯到比较大的地方
else if (dp[i - 1][j] > dp[i][j - 1])
{
i -- ;
}
else
{
j -- ;
}
}
reverse(ans.begin(), ans.end());
cout << ans << '\n';
return ;
}J ~ L 最长上升子序列（LIS）
给出一个由 n 个不超过 1e6 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。
最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。这里有一个视频详细地讲解了一下
对于从n^2优化到nlogn的核心是对寻找最大值的过程进行优化。
J O(n^2)算法
开一个一维dp数组，dp[i]表示从第1到i个数的LIS的值。更新时，只要找到满足小于第 i 个数，且dp最大的数再加上1即可。最后输出dp数组中最大的那个。代码如下：
int n; cin >> n;
vector<int> a(n + 1), dp(n + 1);
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ )
{
int tmp = 0;
for (int j = 1; j < i; j ++ )
{
if (a[j] < a[i]) tmp = max(dp[j], tmp);
}
dp[i] = tmp + 1;
}
int mx = -1;
for (int i = 1; i <= n; i ++)
mx = max(mx, dp[i]);
cout << mx << '\n';K nlogn算法
nlogn算法有很多种优化，如果愿意甚至可以上线段树。这里采用二分+贪心法来优化。
二分+贪心并不能算是严格的dp。但既然是dp专题就也开dp数组吧。
更新dp[i]的过程是，如果当前的数比dp中的所有的数都要大，那么就加到dp的末尾。否则就把第一个比当前的数大的位置换成当前的数。从直觉上来讲，只有前面的数尽可能的小，才更有可能增加新的数，dp的长度才更有可能被增加。同时，由于更换的操作并不会改变dp的长度，所以是可取的。
严格的贪心证明过程可以看视频。
代码如下：
void solve()
{
int n; cin >> n;
vector<int> a(n), dp;
for (int i = 0; i < n; i ++ ) cin >> a[i];
for (int i = 0; i < n; i ++ )
{
auto it = lower_bound(dp.begin(), dp.end(), a[i]);
if (it == dp.end())
dp.push_back(a[i]);
else
*it = a[i];
}
cout << dp.size() << '\n';
return ;
}L 最长上升子序列 2
有 N 朵花排成一排。 对于每个 i (1≤i≤N)，从左数第 i 朵花的高度和美丽值分别是 h_i 和 a_i。这里，h_1,h_2,…,h_N 都是互不相同的。
太郎想拔掉一些花，使得剩下的花满足以下条件：
剩下花的高度从左到右单调递增。
求剩下花的美丽值之和的最大可能值。朴素做法
朴素做法与 J 题的做法相似。不同之处在于，J 题在循环中要找到长度最大的LIS，而这里要找的是权重最大的。dp数组存储的内容也从最大的LIS变成了最大的权重。
所以，我们默认在循环到 i 时，权重只能取a[i]，再从1到 i – 1 遍历 dp 数组，找到里面权重最大的那一个，并更新到当前的状态。
代码如下：
void solve()
{
int n; cin >> n;
vector<ll> a(n + 1), h(n + 1), dp(n + 1);
for (int i = 1; i <= n; ++ i) cin >> h[i];
for (int i = 1; i <= n; ++ i) cin >> a[i];
for (int i = 1; i <= n; ++ i)
{
ll tmp = a[i]; // 至少选自己
for (int j = 1; j < i; ++ j)
{
if (h[j] < h[i])
tmp = max(tmp, dp[j] + a[i]);
}
dp[i] = tmp;
}
ll mx = 0;
for (int i = 1; i <= n; ++ i)
{
mx = max(mx, dp[i]);
}
cout << mx << '\n';
return ;
}树状数组/线段树优化
很显然，对于n = 1e5的数据范围，上面的n^2的复杂度肯定是会TLE的，所以我们不能那么朴素地去做双循环，我们要进行优化。
由于我现在对于树状数组和线段树还不熟悉，所以后续可能新开一个杂项笔记来记录这些东西，这里就先带过一下。
我们注意到，刚刚查询的时候，对于 i ，找的是在所有高度小于h[i]中，dp最大的那一个。换句话说，我们就是要查询最大前缀，然后单点修改dp[i]的值。查询最大前缀和单点修改都是树状数组的经典功能，所以我们可以使用树状数组来进行优化。
代码如下：
struct BIT
{
int n; vector<ll> tr;
BIT(int n)
{
this->n = n;
tr.resize(n + 1);
}
int lowbit(int x)
{
return x & -x;
}
void update(int x, ll v)
{
while (x <= n)
{
tr[x] = max(tr[x], v);
x += lowbit(x);
}
}
ll query(int x)
{
ll ans = 0;
while (x > 0)
{
ans = max(ans, tr[x]);
x -= lowbit(x);
}
return ans;
}
};
void solve()
{
int n; cin >> n;
vector<ll> a(n + 1), h(n + 1), dp(n + 1);
for (int i = 1; i <= n; ++ i) cin >> h[i];
for (int i = 1; i <= n; ++ i) cin >> a[i];
vector<ll> tmp = h;
sort(tmp.begin() + 1, tmp.end());
tmp.erase(unique(tmp.begin() + 1, tmp.end()), tmp.end());
int m = tmp.size() - 1;
BIT bit(m);
ll ans = 0;
for (int i = 1; i <= n; ++ i)
{
int idx = lower_bound(tmp.begin() + 1, tmp.end(), h[i]) - tmp.begin();
ll mx = bit.query(idx - 1);
ll dp = mx + a[i];
bit.update(idx, dp);
ans = max(ans, dp);
}
cout << ans << '\n';
return ;
}M DAG中的最常路
给你一个有向图 G，它有 N 个顶点和 M 条边。顶点编号是 1,2,…,N，对于每个 i (1≤i≤M)，第 i 条有向边是从顶点 x_i 指向顶点 y_i 。G 不包含有向环。
请你找出 G 中最长有向路径的长度。这里路径长度指的是路径中包含的边数。从这一题开始，dp开始和图论结合了。使用sunglassman牌邻接表存图
其中 y in adj[x] 表示有一条从x指向y的边。
vector<vector<int>> adj(n + 1);
for (int i = 1; i <= m; i ++ )
{
int x, y; cin >> x >> y;
adj[x].push_back(y);
}然后是dfs和dp的步骤。dfs 用于求出到当前节点的最长路径是多少，dp用于保存最优值。
思路就是对当前节点，遍历所有它指向的节点，从中取 dfs 最大的+1的作为当前节点的dp值
vector<int> dp(n + 1);
auto dfs = [&](auto&& self, int u)->int
{
if (dp[u]) return dp[u];
for (auto v : adj[u])
{
dp[u] = max(self(self,v) + 1, dp[u]);
}
return dp[u];
};之后，对于每一个节点都dfs一遍，确定了每个点最好的情况下的最长路是多少。最后再遍历一遍求dp的最大值就是这题的答案。
for (int i = 1; i <= n; i ++ )
dfs(dfs, i);
int mx = -1;
for (int i = 1; i <= n; i ++ )
{
mx = max(mx, dp[i]);
}
cout << mx << '\n';N 树上背包
树上背包好难呜呜呜
抄题解都抄不明白
还是先开后面的题
O 树形dp
给你一棵有 N 个顶点的树，顶点编号从 1,2,…,N 开始。
对于每条边 i (1≤i≤N−1)，第 i 条边连接了顶点 x_i 和 y_i。
太郎决定给每个顶点涂成白色或黑色，但有个限制：不能让两个相邻的顶点都涂成黑色。
请你计算所有满足条件的涂色方案数，结果对 1e9 +7 取模。
约定条件
·输入中的所有数值均为整数。
·1≤N≤1e5
·1≤x_i,y_i≤N
·给定的图是一棵树。这里由于相邻的两个顶点不能同时为黑色。那我们就可以知道，如果子节点为黑色，那么父节点一定不为黑色。如果子节点为白色，那么父节点可黑可白。所以每个节点的黑色的方案数为所有子节点都是白色的方案数相乘，每个节点的白色的方案数等于所有子节点的所有方案数相乘。
有了这样的思路以后，我们就可以通过一个二维的dp数组dp[i][j]来存储方案数。dp[i][j]表示第 i 个结点在第 j 种颜色下的方案数。其中，我们可以规定 j = 0 代表白色，j = 1 代表黑色。至于存树，就用最简单的双向邻接表存图就可以了。
那么，我们此时就能够得到以下的状态转移方程
其中，v为u的相邻子节点
接下来我们来看代码实现
void solve()
{
int n; cin >> n;
vector<vector<int>> adj(n + 1);
for (int i = 1; i < n; i ++ )
{
int x, y; cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
vector dp(n + 1, vector<ll>(2));
auto dfs = [&](auto &&self, int u, int fa) -> void
{
dp[u][0] = 1;
dp[u][1] = 1;
for (auto v : adj[u])
{
if (v == fa) continue;
self(self, v, u);
dp[u][0] = dp[u][0] * (dp[v][0] + dp[v][1]) % R;
dp[u][1] = dp[u][1] * dp[v][0] % R;
}
};
dfs(dfs, 1, 0);
cout << (dp[1][0] + dp[1][1]) % R << '\n';
return ;
}照着公式写就可以了
P 换根DP
有一棵包含 N 个顶点的树。顶点编号为 1,2,…,N。对于每个 i（1≤i≤N−1），第 i 条边连接顶点 x_i 和 y_i。
太郎君打算将每个顶点涂成白色或黑色。此时，需要保证任意两个黑色顶点之间，都可以仅通过黑色顶点相互到达。
给定一个正整数 M。对于每个 v（1≤v≤N），请回答以下问题：
以顶点 v 为黑色的所有顶点染色方案有多少种？请输出对 M 取模的结果。写这题的时候，参考了洛谷的题解AT_dp_v Subtree – 洛谷
这道题目相当于要我们去树中寻找不同连通块的组合数
由于是一个无根树，所以我们可以考虑将其转换为一个以 1 为根的有根树。以便于我们的操作。
对于树，那肯定是经典的邻接表存图了。
vector<vector<int>> adj(n + 1);
for (int i = 1; i <= n - 1; i ++ )
{
int x, y; cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}此时，我们考虑对于每一个节点，如果当前节点染黑，那么其能构成的不同的连通块的个数可以分两个方向考虑：他的儿子们和他的父亲。那么我们需要两个dfs和两个dp。我们这么表示：
先考虑儿子们。
儿子们的情况很简单，只要把所有儿子们在他们儿子们的方向的组合数乘起来就行了。这样说可能有点拗口。用刚刚的数学公式来表示，就是
其中，v 表示 u 的所有子节点。累乘表示在 u 节点染黑的情况下，可以构成这么多个连通块。而加一表示当前的节点无法构成任何连通块，也是一种情况。因此，需要将这两者加起来。
有了思路以后，就可以用代码实现一下这个方向的dfs函数了。相比之下比较简单。
vector<ll> dp1(n + 1);
auto dfs1 = [&](auto &&self, int u, int fa) -> void
{
dp1[u] = 1;
for (auto v : adj[u])
{
if (v == fa) continue;
self(self, v, u);
dp1[u] = dp1[u] * (dp1[v] + 1) % m;
}
};再考虑往爸爸的方向进行dfs
往爸爸的方向，要和其他块联通，他的爸爸首先必须要是黑色。所以爸爸方向的方案数是爸爸为黑色的方案数+1（爸爸为白色的方案数）。而要算爸爸是黑色的方案数，就要知道爸爸往他的爸爸的方向的方案数再乘以爸爸往他其他儿子们方向的方案数。总结成数学公式，就是：
其中 v 表示 u 的兄弟节点， 也就是爸爸的其他儿子们
但是，这里会发现一个问题，对于同一个爸爸的所有儿子，每个儿子都要再求一遍自己的兄弟的累乘，时间复杂度是 O(n^2) 级别的，对于 n = 1e5 级别的数据，肯定会炸掉。所以要考虑一下优化。
翻看了万能的题解以后，发现有一种优化方式，是运用前缀和的思想去预处理前缀积和后缀积
那这样以后，每次中累乘的O(n)的操作就变成了pre[u] * suf[u] 的O(1)的操作了
auto dfs2 = [&](auto &&self, int u, int fa)->void
{
int k = adj[u].size();
vector<ll> pre(k), suf(k);
// 处理前缀积
for (int i = 0; i < k; i ++ )
{
int v = adj[u][i];
if (i == 0) pre[i] = 1;
else pre[i] = pre[i - 1];
if (v != fa) pre[i] = pre[i] * (dp1[v] + 1) % m;
}
// 处理后缀积
for (int i = k - 1; i >= 0; i -- )
{
int v = adj[u][i];
if (i == k - 1) suf[i] = 1;
else suf[i] = suf[i + 1];
if (v != fa) suf[i] = suf[i] * (dp1[v] + 1) % m;
}
for (int i = 0; i < k; i ++ )
{
int v = adj[u][i];
if (v == fa) continue;
ll l = (i == 0 ? 1 : pre[i - 1]);
ll r = (i == k - 1 ? 1 : suf[i + 1]);
dp2[v] = (dp2[u] * l % m * r % m + 1) % m;
self(self, v, u);
}
};最后，只要先做dfs1，再把dp2[1]初始化为1（1号没有父节点，是根节点，只有父节点的方向无法构成任何连通块这一种可能），最后dfs2一下，就能求出所有需要的数据。
最后遍历每个点，把它的dp1和dp2乘起来就是最终答案。
dfs1(dfs1, 1, -1);
dp2[1] = 1;
dfs2(dfs2, 1, -1);
for (int i = 1; i <= n; i ++ )
cout << 1ll * dp1[i] *dp2[i] % m << '\n';Q 数位DP
题目描述
请你计算在区间 1 到 K（含端点）内，有多少个整数满足以下条件，并对 1e9 + 7 取模：
·该整数的十进制各位数字之和是 D 的倍数。做题的时候使用AI辅助。
评论（0）
暂无评论