核心内容摘要
牛娘贝尔：不止是奶香，更是一场舌尖上的奇幻冒险
直接放一篇比较有代表性的数位dp学习的题目链接和标准的题解代码由于题解代码较少就懒得解释更多了关键就是从高位到低位的状态dfs➕记忆化➕对区间答案拆解为前缀差https://www.luogu.com.cn/problem/P13085#include iostream #include vector #include cmath #include cstring #include algorithm using namespace std; typedef long long ll; // dp[pos][pre] // pos: 当前处理到的位数 // pre: 上一位填写的数字 (0-
// 因为 pre 有可能是前导零状态或者初始状态我们在记忆化时通常只记录 leadfalse 的情况 ll dp[20][15]; int a[20]; // 存储把数字拆解后的每一位 // dfs 函数 // pos: 当前位数 // pre: 上一位数字 // lead: 是否处于前导零状态 (true 表示前面全是
// limit: 最高位限制 (true 表示当前位受原数限制) ll dfs(int pos, int pre, bool lead, bool limit) { // 递归边界填完了所有位说明找到了一种合法方案返回 1 if (pos
return 1; // 记忆化搜索 // 如果没有最高位限制且不是前导零状态且该状态已经计算过直接返回 if (!limit !lead dp[pos][pre] ! -
return dp[pos][pre]; // 当前这一位能填的最大数字 // 如果受 limit 限制只能填到 a[pos]否则能填到 9 int up limit ? a[pos] : 9; ll ans 0; // 枚举当前位可能填的所有数字 i for (int i 0; i up; i) { // 判断当前填的 i 是否合法 // 情况 1: 之前全是前导零 if (lead) { if (i
{ // 如果当前继续填 0则继续保持前导零状态pre 不更新(或者传个特殊值这里习惯用-2代表无前驱) // limit 更新如果本来受限且当前填了上限(0up)则继续受限 ans dfs(pos - 1, -2, true, limit (i up)); } else { // 如果当前填了非 0前导零状态结束。
// 因为是第一位有效数字不需要和上一位比较差值直接合法 ans dfs(pos - 1, i, false, limit (i up)); } } // 情况 2: 之前已经有有效数字了 else { // 必须满足题目条件相邻数字之差 2 if (abs(i - pre)
{ ans dfs(pos - 1, i, false, limit (i up)); } } } // 记录状态仅在无限制且非前导零时记录因为 limit 和 lead 特殊情况复用率低 if (!limit !lead) dp[pos][pre] ans; return ans; } // 计算 [1, x] 之间的 Windy 数 ll solve(ll x) { int len 0; // 把数字 x 拆解存入数组比如 123 - a[3]1, a[2]2, a[1]3 while (x) { a[len] x % 10; x / 10; } // 记忆化数组初始化为 -1 // 注意如果是多次询问且 dp 状态与 limit/lead 无关其实 dp 数组只需要 memset 一次。
// 但为了保险和逻辑简单这里每次 solve 都清空实际上这题 dp 数组可以复用放在全局只初始化一次更优 // 本题数据量较小每次初始化也没问题若 TLE 可移到 main 函数外 memset(dp, -1, sizeof(dp)); // 从最高位 len 开始搜pre 初始设为 -2一个不可能干扰