Pixiv - Miracle
10-动态规划初步
820 字
4 分钟
10-动态规划初步
动态规划初步
动态规划本质是把n分图相同结点拆成树，然后把原是相同结点的记忆化，效益函数f只能规定一批元素的总效益，方向有前有后
线性DP
有两种，最大子数组和这种求连续区间的，和最长上升子序列和最长公共子序列这种求序列的
最长公共子序列
对于字符串s，t
假如s[i] == s[j], 有
都不选 = dfs(i - 1, j - 1)
不选s = dfs(i - 1, j)，t是不确定的
不选t = dfs(i, j - 1)，s是不确定的
不选s，假如后续也不选t了则应有dfs(i - 1, j) =dfs(i - 1, j - 1) < 都选，假如后续选了t则dfs(i - 1, j ) = dfs(i - k, j - 1) + 1,由于子串i - k,j - 1是i - 1, j -1的子串，故dfs(i - k, j - 1) <= x,dfs(i - 1, j) <= x + 1，故不需考虑不选其中1个的情况
背包DP
01背包
| 类型 | 求最大值 | 求最小值 |
|---|---|---|
| 至多 (≤ C) | f[0..C] = 0 | 一般不常见（不选就是0，已最小） |
| 恰好 (= C) | f[0] = 0，其余 -∞ | f[0] = 0，其余 +∞ |
| 至少 (≥ C) | 不常见 | f[0] = 0，其余 +∞ |
数位DP
单上界数位dp
一般用于计数算1-n，若是区间[l, r]则通过下列公式计算
区间数位dp
#include <bits/stdc++.h>
using namespace std;using ll = long long;using ull = unsigned long long;using ld = long double;
ll p10[16];ll memo[20][20];bool vis[20][20];string lowS, highS;int n;
ll dfs(int i, bool tl, bool tr, int k) { if (i == n) return 0; if (!tl && !tr && vis[i][k]) return memo[i][k];
int lo = tl ? (lowS[i] - '0') : 0; int hi = tr ? (highS[i] - '0') : 9;
ll best = -1; for (int d = lo; d <= hi; ++d) { bool ntl = tl && (d == lowS[i] - '0'); bool ntr = tr && (d == highS[i] - '0'); ll cur; if (!k && !d) { cur = dfs(i + 1, ntl, ntr, 0); } else cur = 1LL * d * p10[k] + dfs(i + 1, ntl, ntr, k + 1);
best = max(best, cur); }
if (!tl && !tr) { vis[i][k] = 1; memo[i][k] = best; } return best;}
int main() { ios::sync_with_stdio(false);cin.tie(nullptr); int t;cin>>t; p10[0] = 1; for (int i = 1; i < 15; ++i) p10[i] = 10 * p10[i - 1];
while(t--) { ll l,r;cin>>l>>r; highS = to_string(r); string tmp = to_string(l); lowS = string(highS.size() - tmp.size(), '0') + tmp; memset(vis, 0, sizeof vis); n = highS.size();
ll ans = dfs(0, 1, 1, 0); cout << ans << '\n'; }}对于tl = 1, tr = 1的状态只有一条路径转移路径通往该状态，所以不用缓存，tl = 0, tr = 0的状态有多条路径，所以需要缓存避免重复计算。
| 情况 | is_num 放不放进 memo？ |
|---|---|
| 有 mask/k 等变量能区分开没开始 | 不用放（已被隐含编码） |
| 没有其他变量区分，且两种都缓存 | 必须放（否则值混淆） |
| 没有其他变量区分，但只缓存 is_num=true | 不用放（false 只走一次，不缓存） |
| 问题类型 | 前导零有害？ | 需要 is_num？ |
|---|---|---|
| 数位之和 | 无害（贡献 0） | 不需要 |
| 是否含某数字 | 无害（0 不碍事） | 不需要 |
| 数位互不相同 | 有害（假装用了 0） | 需要 |
| 相邻/递增/递减 | 有害（假装有前一位） | 需要 |
| 首位特殊约束 | 有害（谁是首位？） | 需要 |
| 位权/翻转相关 | 有害（位权偏移） | 需要（甚至要 k） |
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
随机文章 随机推荐