hdu2089(数位dp)-白红宇

hdu2089(数位dp)

阅读量：6453 次

发布时间：2019-06-23

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

题意：求区间内不含62和4的数的个数；

解法：数位dp。

int dfs(int pos,int pre,bool limit,bool have)。pos表示dp到的数位位置，pre表示前一个数位的数字。limit表示到此时数是否有下降（此位取数字是否受限制的意思），have表示之前是否有62；4的排除是靠在每次枚举下一位i时不取4就可以；每一个case的dp值都是一样的，所以仅仅须要计算一遍。

代码：

/******************************************************* author:xiefubao*******************************************************/#pragma comment(linker, "/STACK:102400000,102400000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 //freopen ("in.txt" , "r" , stdin);using namespace std;#define eps 1e-8const double pi=acos(-1.0);typedef long long LL;const int Max=10100;const int INF=1000000007;int dp[15][12];int num[20];int p=0;int dfs(int pos,int pre,bool limit,bool have){ if(pos==0) return !have; if(have) return 0; if(!limit&&dp[pos][pre]!=-1) return dp[pos][pre]; int en=limit?num[pos-1]:9; int ans=0; for(int i=0; i<=en; i++) { if(i==4)continue; ans+=dfs(pos-1,i,limit&&i==en,(pre==6&&i==2)); } if(!limit) return dp[pos][pre]=ans; else return ans;}int getans(int t){ if(t==0) return 0; p=0; while(t) { num[p++]=t%10; t/=10; } int ans=0; for(int i=0; i<=num[p-1]; i++) { if(i==4) continue; ans+=dfs(p-1,i,i==num[p-1],0); } return ans-1;}int main(){ int l,r; memset(dp,-1,sizeof dp); while(scanf("%d%d",&l,&r)==2) { if(r==0&&l==0) break; cout<
                 
                  <<'\n'; } return 0;}

转载地址：http://qhyzo.baihongyu.com/

你可能感兴趣的文章