HDU 4734 F(x) DP，数位DP-白红宇

HDU 4734 F(x) DP，数位DP

阅读量：6914 次

发布时间：2019-06-27

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

　　题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=4734

　　题目描述：给出两个数A， B，求出小于B且F(i)小于F(A)的所有i的个数

　　解题思路：典型的数位DP， dfs(int len, int cur, int limit) 表示处理到第len位， F(A)还剩cur，是否限制的答案

　　代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #define lson l, m, rt<<1#define rson m+1, r, rt<<1|1typedef long long LL;using namespace std;//const int maxn = 70000+10;int digit[20];int dp[20][200000]; // digit处理到第i位a还剩n的解决方案int dfs(int len, int cur, int limit) { if( len == -1 ) return cur >= 0; // 所有都判定完了， 如果cur还>=0就证明还有一种方案 if( cur < 0 ) return 0; if( !limit && dp[len][cur] != -1 ) return dp[len][cur]; int ret = 0; int templimit = limit ? digit[len] : 9; for( int i = 0; i <= templimit; i++ ) {; ret += dfs( len-1, cur-i*(1<