首页 > 代码库 > codefroces451D - Count Good Substrings 数位DP

codefroces451D - Count Good Substrings 数位DP

题意:给你n,m 问你n-m中有多少个数首位等于末位。

解题思路:数位DP,从0-n有多少个,这样分开计算,首先把每一位所有可能都枚举出来,然后在一位一位的比对DP

解题代码:

 1 // File Name: 204a.cpp 2 // Author: darkdream 3 // Created Time: 2014年07月25日 星期五 09时16分57秒 4  5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 #define LL long long25 using namespace std;26 LL sum[20];27 LL temp[20];28 LL count(LL n)29 {30    int len = 0;31    LL k = n;32    while(k)33    {34        len ++ ; 35        k/= 10 ; 36    }37  //  printf("%d\n",len);38    if(len == 1)39        return n+1;40    LL ans = sum[len-1];41    int t = len ; 42    int a[20];43    while(n)44    {45       a[t] = n %10 ; 46       n = n/10 ;47       t--;48    }49    for(int i =1 ;i <= len-1;i ++)50    {51         int be; 52         be = i == 1?1:0;53         for(;be < a[i];be++)54         {55           ans += temp[len-i-1]; 56         }57    }58    if(a[len] >= a[1])59        ans ++ ; 60    return ans; 61 }62 int main(){63    LL n ,m;64    temp[0] =1 ;65    temp[1] = 10 ; 66    for(int i =1 ;i <= 17 ;i ++)67        temp[i] = temp[i-1]*10;68    sum[0] = 1; 69    sum[1] = 10; 70    for(int i = 2 ;i <= 19 ;i ++)71    {72        sum[i] = sum[i-1];73        for(int j = 1;j <= 9 ;j ++)74               sum[i] += temp[i-2]; 75    }76   // printf("%I64d\n",count(1));77    scanf("%I64d %I64d",&n,&m);78    printf("%I64d",count(m)-count(n-1)); 79 return 0;80 }
View Code