H 数位DP

题意

给你一个数 $N$ $(N\le10^{100})$，问你符合以下条件的有序对 $(A, B)$ 有几个：

  1. $S(A) \le S(B)$ 其中 $S(x)$ 代表 $x$ 在十进制下的数位和
  2. $0\le B \le A \le N$

思路

  1. 先写一个按数位的暴力 DFS (不要使用全局状态变量)

     // pos: 当前要处理的位
 // digitA: A数字当前位的取值范围 [0, digitA]
 // digitB: B数字当前位的取值范围 [0, digitB]
 // limitA: A数字的取值范围是否被限制 (数位DP常见思想)
 // limitB: B数字的取值范围是否被限制 (数位DP常见思想)
 // delta: S(A) - S(B) 

 int dfs(int pos = 0, int delta = 0, bool limitA = true, bool limitB = true) {
     if (pos == s.size()) return delta > 0;
     // 保证 0 <= A <= N
     int digitA = limitA ? s[pos] - '0' : 9, ans = 0;
     // 暴力 DFS A, B 每一位的情况
     for (int i = 0; i <= digitA; ++i) {
         // 保证 0 <= B <= A <= N
         int digitB = limitB ? i : 9;
         for (int j = 0; j <= digitB; ++j)
             ans = (ans + dfs(pos + 1, delta + j - i, limitA && i == digitA, limitB && j == digitB)) % MOD;
     }
     return ans;
 }

  2. 然后直接记忆化（注意 delta 可能会小于 0）

     #include <bits/stdc++.h>
 using namespace std;
 const int MOD = 1e9 + 7, N = 105, M = 2e3 + 5;
 const int offset = 900;

 string s;
 int dp[N][M][2][2];

 int dfs(int pos = 0, int delta = offset, bool limitA = true, bool limitB = true) {
     if (pos == s.size()) return delta > offset;
     if (~dp[pos][delta][limitA][limitB]) return dp[pos][delta][limitA][limitB];
     int digitA = limitA ? s[pos] - '0' : 9, ans = 0;
     for (int i = 0; i <= digitA; ++i) {
         int digitB = limitB ? i : 9;
         for (int j = 0; j <= digitB; ++j)
             ans = (ans + dfs(pos + 1, delta + j - i, limitA && i == digitA, limitB && j == digitB)) % MOD;
     }
     return dp[pos][delta][limitA][limitB] = ans;
 }

 int main() {
     memset(dp, -1, sizeof(dp));
     cin >> s;
     cout << dfs() << endl;
 }