HDU2089 不要62 数位DP - c++编程基础

数位DP第一道题目，昨晚是做了4个小时，参考了一下方程，最后搞出来了，但是很乱，先给上昨天的代码

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-8 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; int n,m; int dp[10][3];//dp[i][j],前i位数的状态， /* dp[i][0],表示前i位数且不含不吉利数的个数 dp[i][1],表示前i位数开头放了2的数的个数 dp[i][2],表示前i位数含不吉利数的个数 */ int num[12]; void init() { memset(dp,0,sizeof(dp)); dp[0][0] = 1; for(int i=1;i<=6;i++) { dp[i][0] = dp[i-1][0] * 9 - dp[i-1][1];//构造一下前i位不含不吉利数个数，因为最后以为可能取6，与下一步的开头取2凑成了不吉利数，所以减去 dp[i][1] = dp[i-1][0];//开头为2的前i位数 就是不含不吉利数前i-1数 dp[i][2] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] * 10;//含有的话一个是本身就含有，那么到了i位就是i-1位乘10，还有前i-1位数不含有因为多了一个4而产生了，最后就是开头为2，因为6而产生了 } } void clear() { memset(num,0,sizeof(num)); } int cal(int x) { clear(); int cnt = 1; int tmpx = x; while(tmpx) { num[cnt++] = tmpx%10; tmpx /= 10; } num[cnt] = 0; bool flag = false; int ans = 0; for(int i=cnt;i>=1;i--) { ans += dp[i-1][2] * num[i]; if(flag)//已经为不吉利 ans += dp[i-1][0] * num[i]; if(!flag && num[i] > 4)//此位大于4，后面可有4 ans += dp[i-1][0]; if(!flag && num[i+1] == 6 && num[i] > 2)//后一位是6，此位大于2 ans += dp[i][1]; if(!flag && num[i] > 6)//此位大于6 ans += dp[i-1][1]; if((num[i] == 2 && num[i+1] == 6) || num[i] == 4) //导致不吉利 flag = true; } return x - ans; } int main() { init(); while(scanf("%d %d",&n,&m), n + m) { clear(); int ans = cal(m+1) - cal(n); printf("%d\n",ans); } return EXIT_SUCCESS; }

今天想回头再去看看，最后发现百度里有一个数位DP的文档还是很不错的

http://wenku.baidu.com/link url=o3ER_gVCyB0qcKthM-Y8vPtAGZ_u5bzOu_gUCUhPcXC6YfaSDgtBSXNEEvvGvSzyuDE9TULcPNsDrRd9IUtQVHeKUVrnPUjyfWjCly_J7Xq

这个文档非常好，而且里面有这道题目的剖析，做法跟我昨天的不一样，但是更好理解，所以按照他的剖析自己写了一下，做出来了，还是比较开心的，忍不住多赞一下这个文档，给出新思路的代码

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-8 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; int dp[12][12];//开头为j的i位数 int num[10]; void clear() { memset(dp,0,sizeof(dp)); dp[0][0] = 1; for(int i=1;i<=6;i++) { for(int j=0;j<10;j++) { for(int k=0;k<10;k++) { if(j != 4 && (j != 6 || k != 2)) dp[i][j] += dp[i-1][k]; } } } } int cal(int x) { memset(num,0,sizeof(num)); int cnt = 1; int tmpx = x; while(tmpx) { num[cnt++] = tmpx%10; tmpx /= 10; } int ans = 0; for(int i=cnt;i>=0;i--) { for(int j=0;j