1 /* 2 找规律/数位DP：我做的时候差一点做出来了，只是不知道最后的 is_one () 3 http://www.cnblogs.com/crazyapple/p/3315436.html 4 数位DP：http://blog.csdn.net/libin56842/article/details/11580497 5 */ 6 #include7 #include 8 #include 9 #include 10 #include 11 #include 12 using namespace std;13 14 const int MAXN = 1e5 + 10;15 const int INF = 0x3f3f3f3f;16 17 int is_one(long long n)18 {19 long long m = n;20 long long i = n / 10 * 10;21 22 for (; i<=m; ++i)23 {24 long long tmp = i; int sum = 0;25 while (tmp)26 {27 sum += tmp % 10;28 tmp /= 10;29 }30 if (sum % 10 == 0) return 1;31 }32 33 return 0;34 }35 36 long long get_num(long long n)37 {38 if (n < 0) return 0;39 if (n <= 10) return 1;40 41 return n/10 + is_one (n);42 }43 44 int main(void) //HDOJ 4722 Good Numbers45 {46 //freopen ("G.in", "r", stdin);47 48 int t, cas = 0;49 long long l, r;50 scanf ("%d", &t);51 while (t--)52 {53 scanf ("%I64d%I64d", &l, &r);54 55 printf ("Case #%d: %I64d\n", ++cas, get_num (r) - get_num (l-1));56 }57 58 return 0;59 }60 61 62 /*63 Case #1: 064 Case #2: 165 Case #3: 166 */
1 /* 2 数位DP：基础题，对于一个数，把它每位数分出来，从最高位开始枚举。dp[i][(j+k)%10] += dp[i+1][j]; 3 dp[i][j]表示前i位数和取模是j的个数 4 */ 5 #include6 #include 7 #include 8 #include 9 using namespace std;10 11 typedef long long ll;12 const int MAXN = 22;13 const int INF = 0x3f3f3f3f;14 ll dp[MAXN][MAXN];15 int dig[MAXN];16 17 ll work(ll n) {18 ll tmp = n; int len = 0;19 memset (dig, 0, sizeof (dig));20 while (tmp) {21 dig[++len] = tmp % 10;22 tmp /= 10;23 }24 memset (dp, 0, sizeof (dp)); int x = 0;25 for (int i=len; i>=1; --i) {26 for (int j=0; j<10; ++j) {27 for (int k=0; k<10; ++k) {28 dp[i][(j+k)%10] += dp[i+1][j];29 }30 }31 for (int j=0; j