HDU3555 Bomb 数位DP - c++编程基础

过题率一点都不高，看着有点吓人，刚开始想不出来，网上的代码思路很相似，都是dp[i][j],一维代表位数二维代表状态，状态分三种，含49，不含49，不含49但是以9开头，从一开始我的想法跟这个就不搭边啊，后来自己沿着原来的思路继续想下去，发现也是可以的，而且感觉比分三种状态的要好理解，当然还有一种记忆化搜索的更好理解

我的思路；dp[i][j],以j开头的i位数不含49的个数，这样预处理起来其实非常方便，三层循环，第一层代表位数，第二层第三层代表相邻两个位置上的数的情况，边界值dp[0][0]=1；预处理好以后把输入的数分解，然后从高位到低位开始找出所有不含49 的个数，然后题目求的是不含有的那么答案其实就是

n减去不含有49的个数就是含有的了

#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; ll dp[25][12];//j开头的i位数 ll num[112]; void clear() { memset(dp,0,sizeof(dp)); dp[0][0] = 1; for(int i=1;i<=20;i++) { for(int j=0;j<10;j++) { for(int k=0;k<10;k++) { if(j != 4 || k != 9) dp[i][j] += dp[i-1][k]; } } } } ll cal(ll x) { memset(num,0,sizeof(num)); ll cnt = 1; ll tmpx = x; while(tmpx) { num[cnt++] = tmpx%10; tmpx /= 10; } ll ans = 0; for(ll i=cnt;i>=0;i--) { for(ll j=0;j