codefroces204A - Little Elephant and Interval 数位DP-白红宇

codefroces204A - Little Elephant and Interval 数位DP

阅读量：5115 次

发布时间：2019-06-13

本文共 1478 字，大约阅读时间需要 4 分钟。

题意：给你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
      
        6 #include
       
         7 #include
         8 #include
         
           9 #include
          
           10 #include
           
            11 #include
            
             12 #include
             
              13 #include
              
               14 #include
               
                15 #include
                
                 16 #include
                 
                  17 #include
                  
                   18 #include
                   
                    19 #include
                    
                     20 #include
                     
                      21 #include
                      
                       22 #include
                       
                        23 #include
                        
                         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 }