DAG DP
约 1989 字大约 7 分钟
2025-07-13
概念
01DP和前缀DP都有明显的层次结构。
而更一般的DP对应的DAG图更无序,这时我们难以用for循环便利状态。
例题
1 巴比伦塔
UVA437 巴比伦塔
有很多块🧱,长宽高是
x, y, z(可以任意旋转),每种都有无数个,现在想要将🧱叠加起来搭一个最高的塔,要求是上面的🧱的长宽要严格小于下面的🧱。例如: 输入:
2 6 8 10 5 5 5
输出:
21
解释:第一块选择 (10,8),第二块选择 (8,6),第三块选择(5,5)。
做法
砖块有六种,所以可认为总共有6 * n个砖块。
状态:以某个砖块为塔顶,所能搭成的最大高度。
转移:转移到比它长宽小的砖块。
对于 u→v,fv=max(fu+vu∣u∈V,wv<wu,hv<hu)
代码
BFS
记录入度(有多少个状态转移到自身),当前序状态都计算好后,才可以计算开始从自身转移。
// https://www.luogu.com.cn/problem/UVA437
void work(int n, int cnt) {
vector<t3i> a;
for (int i = 0; i < n; ++i) {
int x, y, z;
cin >> x >> y >> z;
a.emplace_back(x, y, z);
a.emplace_back(x, z, y);
a.emplace_back(y, x, z);
a.emplace_back(y, z, x);
a.emplace_back(z, x, y);
a.emplace_back(z, y, x);
}
n *= 6;
auto adj = vector(n, vector<int>());
vector<int> in(n);
// 建图
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
auto [x1, y1, z1] = a[i];
auto [x2, y2, z2] = a[j];
if (x1 > x2 && y1 > y2) {
adj[i].push_back(j);
in[j]++;
}
}
}
queue<int> q;
vector<int> dp(n);
for (int i = 0; i < n; ++i) {
auto &[x, y, z] = a[i];
dp[i] = z;
if (in[i] == 0) q.push(i);
}
while (!q.empty()) {
auto u = q.front();
q.pop();
for (auto v : adj[u]) {
in[v]--;
auto &[x, y, z] = a[v];
dp[v] = max(dp[v], dp[u] + z);
if (in[v] == 0) q.push(v);
}
}
// dout << dp;
cout << "Case " << cnt << ": maximum height = "
<< *max_element(all(dp)) << '\n';
}DFS
记忆化搜索,天然带有顺序,在计算一个状态时,会先尝试计算所有能到这个状态的状态。
vector<int> dp(n, -1);
function<int(int)> dfs = [&](int v) {
if (dp[v] != -1) return dp[v];
auto [x1, y1, z1] = a[v];
dp[v] = z1;
for (int i = 0; i < n; ++i) {
auto [x2, y2, z2] = a[i];
if (x2 > x1&& y2 > y1) {
dp[v] = max(dp[v], dfs(i) + z1);
}
}
return dp[v];
};
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, dfs(i));
}
cout << ans << '\n';转换
排序,小的在前,大的在后,在计算一个状态的时,前置状态一定被计算了。 ![[巴比伦塔转换.svg]]
vector<int> dp(n);
for (int i = 0; i < n; ++i) {
auto [x1, y1, z1] = a[i];
dp[i] = max(dp[i], z1);
for (int j = i + 1; j < n; ++j) {
auto [x2, y2, z2] = a[j];
if (x2 > x1&& y2 > y1) {
dp[j] = max(dp[j], dp[i] + z2);
}
}
}
cout << *max_element(all(dp)) << '\n';换个方向可能会更好理解:
for (int i = 0; i < n; ++i) {
auto [x1, y1, z1] = a[i];
dp[i] = z1;
for (int j = i - 1; j >= 0; --j) {
auto [x2, y2, z2] = a[j];
if (x2 < x1&& y2 < y1) {
dp[i] = max(dp[i], dp[j] + z1);
}
}
}
cout << *max_element(all(dp)) << '\n';2 最长递增子序列
LeetCode.300 给你一个整数数组
nums,找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,
[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。
做法
状态:fi 表示只选择前 i 个数字,且选择了最后一个数字得到的最长子序列长度。
转移(省略了亿些线):
代码
vector<int> dp(n, 1);
for (int i = 0; i < n; ++i) {
for (int j = i - 1; j >= 0; --j) {
if (a[j] >= a[i]) continue;
dp[i] = max(dp[j] + 1, dp[i]);
}
}
cout << *max_element(all(dp)) << endl;for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (a[j] <= a[i]) continue;
dp[j] = max(dp[i] + 1, dp[j]);
}
}状态压缩
一个状态,有三个信息:坐标 i, 值 a[i] ,dp[i]。
我们之前的DP,也可以理解为用坐标来压缩信息。
如果我们换作用a[i]来压缩: 相当于开了一个非常大(值范围)的数组,数组的下标代表的是值,答案是历史上以这个值为结尾的最长递增子序列长度。
此处用到[[树状数组BIT]]O(logn)查找小于当前值的最长子序列长度。
// 离散化,转化为排名(从1开始)
vector<int> rk = arr;
sort(all(rk));
rk.erase(unique(all(rk)), rk.end());
int m = rk.size(), n = arr.size();
for (int i = 0; i < n; ++i) {
arr[i] = lower_bound(all(rk), arr[i]) - rk.begin() + 1;
}
vector<int> t(m + 1);
auto qry = [&](int i, int init = 0) {
int res = init;
for (; i > 0; i -= i & -i) {
res = max(t[i], res);
}
return res;
};
auto upd = [&](int i, int k = 1) {
for (; i < t.size() && i > 0; i += i & -i) {
t[i] = max(t[i], k);
}
};
for (auto x : arr) {
upd(x, qry(x - 1) + 1);
}
cout << qry(m) << endl;如果以dp[i]进行状态压缩:
将结果作为状态,是一个比较难想到的状态设计。有些题正常状态难以设计,或者数据量大,这时不妨想想将结果作为状态(前提条件:结果的可能性非常小(?))
状态:答案为 k 时,结尾的最小值。
转移:找到第一个小于自己的 x ,为 dp[idx],用 x 更新 dp[idx+1]。
vector<int> ans;
for (auto x : arr) {
int idx = lower_bound(all(ans), x) - ans.begin();
if (idx == ans.size()) ans.push_back(x);
else ans[idx] = x;
}
cout << ans.size();3 数塔 & 矩阵
LeetCode.64 最小路径和
给定一个包含非负整数的
*m* x *n*网格grid,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。说明: 每次只能向下或者向右移动一步。 ![[最小路径和.svg]]
int m = grid[0].size(), n = grid.size();
vector<int> dp(m, 1e9);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (i > 0&& j > 0) dp[j] = min(dp[j], dp[j - 1]) + grid[i][j];
else if (i == 0&& j > 0) dp[j] = dp[j - 1] + grid[i][j];
else if (i > 0&& j == 0) dp[j] = dp[j] + grid[i][j];
else dp[j] = grid[i][j];
}
}
cout << dp[m - 1] << endl;贸易航线
链接🔗:P12214 蓝桥杯 2023 国 Python B 贸易航线
每件物品可以买不止一次??
![[贸易航线.svg|250]]
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, m, k;
cin >> n >> m >> k;
auto goods = vector(n, vector<int>(m));
auto adj = vector(n, vector<pii>());
for (auto& row : goods) for (auto& x : row) cin >> x;
for (int i = 0; i < n - 1; ++i) {
adj[i].emplace_back(i + 1, 0);
}
for (int col = 0; col < m; ++col) {
int cur = 0;
while (cur < n&& goods[cur][col] == -1) cur++;
for (int row = 0; row < n; ++row) {
while (row < n&& goods[row][col] == -1) row++;
if (row == n) break;
int diff = goods[row][col] - goods[cur][col];
if (diff > 0) {
adj[cur].emplace_back(row, diff);
}
cur = row;
}
}
vector<ll> dp(n);
for (int u = 0; u < n; ++u) {
for (auto [v, w] : adj[u]) {
dp[v] = max(dp[u] + w, dp[v]);
}
}
cout << dp[n - 1] * k;
}数组切分
链接🔗:数组切分
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(0)->sync_with_stdio(0);
const int mod = 1e9 + 7;
int n; cin >> n;
vector<int> a(n);
vector<ll> dp(n + 1);
for (int i = 0 ; i < n; ++i) cin >> a[i];
dp[0] = 1;
for (int i = 0; i < n; ++i) {
int maxx = a[i], minn = a[i];
for (int j = i; j < n; ++j) {
maxx = max(a[j], maxx), minn = min(a[j], minn);
if (maxx - minn == j - i) {
(dp[j + 1] += dp[i]) %= mod;
}
}
}
cout << dp[n] << endl;
}魔法阵
链接🔗:P12332 蓝桥杯 2023 省 Java B 魔法阵
![[魔法阵.svg|500]]
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(0)->sync_with_stdio(0);
const ll INF = 1ll << 31;
int n, k, m;
cin >> n >> k >> m;
auto adj = vector(n, vector<pii>());
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
vector<ll> diss(n, INF), dise(n, INF);
auto dij = [&](int s, vector<ll>& dis) {
priority_queue<pii, vector<pii>, greater<pii>> q;
vector<int> vis(n);
q.emplace(0, s);
dis[s] = 0;
while (!q.empty()) {
auto [d, u] = q.top();
q.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto [v, w] : adj[u]) if (d + w < dis[v]) {
dis[v] = d + w;
q.emplace(dis[v], v);
}
}
};
dij(0, diss), dij(n - 1, dise);
ll ans = diss[n - 1];
for (int i = 0; i < n; ++i) {
queue<int> q;
q.push(i);
for (int j = 0; j < k; ++j) {
vector<int> vis(n);
int sz = q.size();
while (sz--) {
auto u = q.front();
q.pop();
for (auto [v, _] : adj[u]) if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
while (!q.empty()) {
auto u = q.front();
q.pop();
ans = min(diss[i] + dise[u], ans);
}
}
cout << ans;
}