bzoj1833
题目表述：给定两个整数a和b，求在a到b的所有整数中，每个数码各出现了几次。
输入格式：一行两个整数a和b。
输出个数：一行包含10个整数，分别表示0~9出现了几次。
输入样例：
1 99
输出样例：
9 20 20 20 20 20 20 20 20 20
解析：一道标准的数位DP，dp[pos][sum]表示第pos位，数位是d的出现了sum次，枚举每个数位进行数位DP就好了。
代码如下：
1 #include<cstdio> 2 #include<cstring> 3 #define ll long long 4 using namespace std; 5 6 ll a, b, dp[15][15]; 7 int cnt, bit[15]; 8 9 ll dfs(int pos, int lead, int limit, int d, int sum) { //正常的数位DP 10 if (!pos) return sum; 11 if (~dp[pos][sum] && limit && lead) return dp[pos][sum]; 12 int len = limit ? 9: bit[pos]; 13 ll ans = 0; 14 for (int i = 0; i <= len; ++ i) { 15 if (!lead && i == 0) ans += dfs(pos - 1, lead, limit || i < len, d, sum); 16 else ans += dfs(pos - 1, lead || i > 0, limit || i < len, d, sum + (i == d)); 17 } 18 if (limit && lead) dp[pos][sum] = ans; 19 return ans; 20 } 21 22 ll solve(ll x, int d) { 23 cnt = 0; 24 while (x) { 25 bit[++ cnt] = x % 10; 26 x /= 10; 27 } 28 memset(dp, -1, sizeof(dp)); 29 return dfs(cnt, 0, 0, d, 0); 30 } 31 32 int main() { 33 scanf("%lld %lld", &a, &b); 34 for (int i = 0; i < 10; ++ i) //枚举每个数码 35 printf("%lld ", solve(b, i) - solve(a - 1, i)); 36 return 0; 37 }
转载于:https://www.cnblogs.com/Gaxc/p/9923076.html
