题意 : 统计[a, b]之间所有数的含0个数之和。
思路 : 数位DP,用了GYZ的记忆话搜索写法,注意下一个数的前缀0不算进去就OK了的, 简单题。
#include <cstdio> #include <cstring> typedef long long lld; lld dp[15][11][15][2], n, m; int bit[15]; lld dfs(int len, int x, int sum, int s, int fp){ if (len == 0){ return (lld)(sum + s); } if (!fp && dp[len][x][sum][s] != -1)return dp[len][x][sum][s]; int Max = (fp ? bit[len] : 9); lld ret = 0; for (int i = 0; i <= Max; i++){ ret += dfs(len-1, i, sum + (!s && i == 0), s && i == 0, fp && i == Max); } if (!fp) dp[len][x][sum][s] = ret; return ret; } lld solve(lld x){ if (x < 0)return 0; else if (x == 0)return 1; int len = 0; while (x){ bit[++len] = x % 10; x /= 10; } return dfs(len, bit[len], 0, 1, 1); } int main(){ int T; scanf("%d", &T); memset(dp, -1, sizeof(dp)); for (int cas = 1; cas <= T; cas++){ scanf("%lld%lld", &n, &m); printf("Case %d: %lld\n", cas, solve(m) - solve(n-1)); } return 0; }