hdu 4734 F(x) 数位dp - c++编程基础

题意：定义 F(x) = A_n * 2^n-1 + A_n-1 * 2^n-2 + ... + A₂ * 2 + A₁ * 1(其中 x = A_nA_n-1A_n-2 ... A₂A₁)，那么给定A，B，求[0，B]区间的i，满足F(i)<=F(A)

的个数。

思路：设dp[ pos ] [ k ]为当前考虑pos位，之后(pos + 1)位与之前的位数组合形成的F函数值不超过k的数的个数，详见代码：

/*********************************************************
  file name: hdu4734.cpp
  author : kereo
  create time:  2015年01月20日 星期二 11时09分03秒
*********************************************************/
#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             using namespace std; typedef long long ll; const int sigma_size=26; const int N=10; const int MAXN=6000+50; const int inf=0x3fffffff; const double eps=1e-8; const int mod=100000000+7; #define L(x) (x<<1) #define R(x) (x<<1|1) #define PII pair
            
              #define mk(x,y) make_pair((x),(y)) int res; int bit[N],dp[N][MAXN],a[N],p[N]; int dfs(int pos,int st,int flag){ if(pos == -1) return 1; if(flag && dp[pos][st]!=-1) return dp[pos][st]; int ans=0; int x=flag ? 9 : bit[pos]; for(int i=0;i<=x;i++){ int k=st-(int)p[pos]*i; if(k<0) continue; ans+=dfs(pos-1,k,flag || i