算法数位DP(按位DP) hdoj 2089 hdoj 3555 uestc 1307 基础题-白红宇

算法数位DP(按位DP) hdoj 2089 hdoj 3555 uestc 1307 基础题

阅读量：5307 次

发布时间：2019-06-14

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

按位dp：对于当前长度i是枚举该为的值(0~10),统计出区间内合法的数；

下面是基础入门的3题；

hdoj 2089 区间数内不包含4和62的数的个数

View Code

1  #include 
      
        2  #include 
       
         3  #include 
        
          4  #include 
         
           5  using namespace std; 6  7  8  int num[10][10]; 9 10  // 预处理长度为i，取值为j时的合法元素个数；11  void Pre(){12      memset(num, 0, sizeof num);13      for ( int i=0; i<10; ++i )14         num[1][i] = 1;15      num[1][4] = 0;16      for ( int i=2; i<9; ++i )17      {18          for ( int j=0; j<10; ++j ) if(j ^ 4)19            for ( int k=0; k<10; ++k ) if(k ^ 4)20            {21                if(j==6 && k==2) continue; // 剔出非法的元素22                num[i][j] += num[i-1][k];23            }24      }25  };26 27  int count( int n ) {28       if(n <= 0) return 1;29       int a[12] = {
    0};30       while(n ) {31           a[++a[0] ] = n%10; n /= 10;32       }33       int ret = 0, last=-1;34       while(a[0] > 0) {35            int t = a[a[0] ];36            for ( int i=0; i
          
            R) swap(L, R);56            int l = count(L-1);57            int r = count(R);58            printf("%d\n", r-l);59      }60  };

hdoj 统计区间出现字串49的个数

View Code

1 #include 
      
        2  #include 
       
         3  #include 
        
          4  #include 
         
           5  using namespace std; 6  7  typedef __int64 ll; 8  9  ll dp[30][10][2];10  // dp[i][j][0] 表示长度为i取值为j的不合法的元素个数；11  // dp[i][j][1] 表示长度为i取值为j的合法元素个数12 13  void Pre(){14      memset(dp, 0, sizeof dp);15      for ( int i=0; i<10; ++i ){16          dp[1][i][0] = 1;17      }18      for ( int i=2; i<30; ++i )19      {20          for ( int j=0; j<10; ++j )21          for ( int k=0; k<10; ++k ){22               if(!(j==4 && k==9) )23                dp[i][j][0] += dp[i-1][k][0];24               dp[i][j][1] += dp[i-1][k][1];25               if(k == 9 && j == 4)26                 dp[i][j][1] += dp[i-1][k][0];27          }28      }29      //for ( int i=0; i<10; ++i )30      // cout << dp[4][i][1] <<" "; puts("");31  };32 33  // 这里也要注意数据类型34  ll get(int *a, int l, int r){35     ll ret = 0;36     for(int i=l; i>=r; --i)37      ret = ret*10+a[i];38     return ret;39  }40 41  void count( ll n ){42      if(n < 49){43          puts("0");  return ;44      }45      int a[30]={
    0};46      while(n ) {47          a[++a[0] ] = n%10; n /= 10;48      }49      ll ret = 0;50      int last = -1;51      while(a[0] > 1) {52          int t = a[a[0] ];53          for ( int i=0; i

uestc 统计区间内符合相邻数字差大于1的数；

View Code

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6  7 typedef long long ll; 8  9 ll dp[15][12];10 bool ok(int x, int y){11     return abs(x-y)>1;12 }13 14 void Pre(){15     memset(dp, 0, sizeof dp);16     for ( int i=0; i<10; ++i )17        dp[1][i] = 1;18     for ( int i=2; i<12; ++i ){19         for ( int j=0; j<10; ++j )20         {21             for ( int k=0; k<10; ++k )if(ok(j, k) ) {22                 dp[i][j] += dp[i-1][k];23             }24         }25     }26    /* for(int j=1; j<=3; puts(""), ++j )27     for ( int i=0; i<10; ++i )28       cout << dp[j][i] << " ";*/29 }30 31 ll count( ll x ) {32      int a[14]={
    0};33      while( x ) {34          a[++a[0] ] = x%10; x /= 10;35      }36      ll ret = 0;37      for ( int i=1; i
          
            0 ) {42          int t = a[a[0] ];43          for ( int i=(last==20?1:0); i