hdu2089(数位dp) - c++编程基础

TOP

hdu2089(数位dp)

2015-07-24 06:51:50 来源: 作者: 【大中小】浏览:51次

Tags：hdu2089 (数位

题意：求区间内不含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-8 const 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<


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：从零单排PAT1015,1016,1017,1018	下一篇：并行编程之条件变量（posix condi..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: