喵

AmaoFox · 2025-06-21 16:51:37 · 题解

喵呜。本喵就大发慈悲地讲解一下这道整齐的数的题解喵。(≧ω≦)

大意

给定一个上界数 n 和阈值 m，统计 [0, n] 范围内所有整齐的数的个数喵。一个数是整齐的，当且仅当它所有相邻数位差的绝对值之和不超过 m 喵。比如数 123 的和是 |1-2|+|2-3|=2 喵。

思路

喵哼哼。这种数字统计问题当然要用数位 DP 解决喵。本喵会用一个记忆化搜索来优雅地处理喵。(ฅ´ω`ฅ)

状态设计

本喵设计的状态是：dp[pos][last][sum][tight]喵～解释一下：

• pos：当前处理到第几位；（从高到低喵）
• last：上一位的数字；（如果前面都是 0，用 10 表示喵）
• sum：当前相邻数位差的绝对值之和；
• tight：是否紧贴上界。（前面选的数都和 n 一样喵）

状态转移

分两种情况处理喵：

• 前导零状态（last == 10）
  • 选 0：保持前导零状态喵。
  • 选非 0：结束前导零，更新 last 但 sum 仍然是 0。（因为是第一位喵）
• 正常状态
  • 计算当前位与上一位的差 `diff = abs(last - d)。
  • 如果 sum + diff > m 就跳过。否则更新 sum += diff。

当处理完所有位数时（pos == len），就返回 1 喵。

代码

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 20, M = 205;

int dp[N][11][M][2];
string s;
int m;
int len;

int dfs(int pos, int last, int sum, bool tight) {
  if (pos == len) {
    return (sum <= m) ? 1 : 0;
  }
  if (dp[pos][last][sum][tight] != -1) {
    return dp[pos][last][sum][tight];
  }
  int up = tight ? (s[pos] - '0') : 9;
  int res = 0;
  for (int d = 0; d <= up; d++) {
    if (last == 10) {
      int new_last = (d == 0) ? 10 : d;
      int new_sum = sum;
      bool new_tight = tight && (d == up);
      res += dfs(pos + 1, new_last, new_sum, new_tight);
    } else {
      int diff = abs(last - d);
      int new_sum = sum + diff;
      if (new_sum > m) {
        continue;
      }
      bool new_tight = tight && (d == up);
      res += dfs(pos + 1, d, new_sum, new_tight);
    }
  }
  return dp[pos][last][sum][tight] = res;
}

signed main() {
  int n;
  cin >> n >> m;
  s = to_string(n);
  len = s.size();
  memset(dp, -1, sizeof(dp));
  cout << dfs(0, 10, 0, 1);
}

喵呜。说实话本喵为了题解写了一些比较“规范”的变量名，看着觉得完全是 AI 写的喵。

由于记忆化的存在，时间复杂度显然和空间复杂度是一样的喵，因为每个状态只计算一次，之后就直接调用了喵。

很重要的建议喵！表示当前处于前导 0 的状态，把 last 设置成 \bold{10} 是最方便的做法了喵。真不要和本喵早年一样单开一维然后把自己累死了喵。

哼。本喵的讲解就到这里喵。要好好理解状态设计的意义喵，这才是数位 DP 的精髓喵。(๑•̀ㅂ•́)و✧

唉我怎么又写了一篇莫名其妙的东西。