这题数位DP很不一样。。首先不能像常规的数位DP 用[0,R] 减去[0, L]
用类似字典树的方法,一个10进制数的区间也可以表示成一棵十叉树,每条路径就是一个数字,那么令 dp[h][sum][rem],代表当前h位下,前几位的和为sum,前一个子树剩余的数字个数,这样去进行数位DP,把在边界的值搜到底,然后其他位置就可以进行记忆化,时间复杂度可以接受
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; char l[20], r[20]; int k, n, vis[20][200][1005]; struct Node { ll cnt, rem; Node () {} Node (ll cnt, ll rem) { this->cnt = cnt; this->rem = rem; } Node operator += (Node c) { cnt += c.cnt; rem = c.rem; return *this; } } dp[20][200][1005]; Node dfs(int h, int sum, int rem, int f1, int f2) { if (h == n) { if (sum + rem >= k) return Node(1, 0); return Node(0, sum + rem); } if (vis[h][sum][rem] && f1 && f2) return dp[h][sum][rem]; Node ans = Node(0, rem); int low = f1 ? 0 : l[h] - '0'; int up = f2 ? 9 : r[h] - '0'; for (int i = low; i <= up; i++) ans += dfs(h + 1, sum + i, ans.rem, (f1 || i != low), (f2 || i != up)); if (f1 && f2) { vis[h][sum][rem] = 1; dp[h][sum][rem] = ans; } return ans; } int main() { while (~scanf("%s%s%d", &l, &r, &k)) { memset(vis, 0, sizeof(vis)); n = strlen(r); int m = strlen(l); for (int i = m - 1; i >= 0; i--) l[i + n - m] = l[i]; for (int i = 0; i < n - m; i++) l[i] = '0'; printf("%lld\n", dfs(0, 0, 0, 0, 0).cnt); } return 0; }