喵哈哈的日常选数问题 Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others) Problem Description
喵哈哈村子的TTT同学比较怪,,他非常讨厌一类数字,是哪种呢?
就是讨厌那些含有37或者4的数
比如 21379,123485,12379。
但是他并不讨厌928357这个数,因为他即不包含37,也没有4。
现在你[L,R]的区间,问你在这个区间中,最多能够选出多少个TTT同学不讨厌的数呢? Input
输入两个整数,表示L和R
1 <= L <= R <= 2000000000 。 Output 输出一个整数,表示选出的数的个数 Sample Input
1 10
Sample Output
9
解题思路:数位DP
#include <cstdio>int DP[15][15];int solve(int n) {int cnt = 0, ans= 0, num[15];while (n > 0) {num[++cnt] = n % 10;n /= 10;}num[cnt+1] = 0;for (int i = cnt; i > 0; i–) {for (int j = 0; j < num[i]; j++) {if (j != 4 && !(num[i+1] == 3 && j == 7))ans += DP[i][j];}if (num[i] == 4 || (num[i] == 7 && num[i+1] == 3))break;}return ans;}int main() {int L, R;DP[0][0] = 1;for (int i = 1; i <= 10; i++)for (int j = 0; j < 10; j++)for (int k = 0; k < 10; k++)if (j != 4 && !(j == 3 && k == 7))DP[i][j] += DP[i-1][k];while (scanf(“%d%d”, &L, &R) != EOF)printf(“%d\n”, solve(R+1) – solve(L));return 0;}
每个人在他的人生发轫之初,总有一段时光,