hdu3555——Bomb（数位dp）-白红宇

hdu3555——Bomb（数位dp）

阅读量：2343 次

发布时间：2019-05-10

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

Problem Description

The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence “49”, the power of the blast would add one point.

Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?

Input

The first line of input consists of an integer T (1 <= T <= 10000), indicating the number of test cases. For each test case, there will be an integer N (1 <= N <= 2^63-1) as the description.

The input terminates by end of file marker.

Output

For each test case, output an integer indicating the final points of the power.

Sample Input

500

Sample Output

这题跟不要62有点区别，最后的状态要判断下，相比之下复杂了点。并且不能直接算出没有49的数，当然也可能是我没想到正确的做法

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #define INF 0x3f3f3f3f#define MAXN 10000000005#define Mod 10001using namespace std;int dight[30];long long dp[30][3];long long dfs(int pos,int s,bool limit){ if(pos<0) return s==2; //求符合条件的数与求不符合条件的区别 if(!limit&&dp[pos][s]!=-1) return dp[pos][s]; int end; long long ret=0; if(limit) end=dight[pos]; else end=9; for(int d=0;d<=end;++d) { int have=s; if(s==1&&d==9) have=2; //有了49，后面就随便填了 if(s==0&&d==4) have=1; //有了4，要注意后面是否会有9 if(s==1&&d!=4&&d!=9) have=0; //不用注意了 ret+=dfs(pos-1,have,limit&&d==end); } if(!limit) dp[pos][s]=ret; return ret;}long long solve(long long a){ memset(dight,0,sizeof(dight)); int cnt=0; while(a!=0) { dight[cnt++]=a%10; a/=10; } return dfs(cnt-1,0,1);}int main(){ memset(dp,-1,sizeof(dp)); int t; scanf("%d",&t); long long n; while(t--) { scanf("%I64d",&n); printf("%I64d\n",solve(n)); } return 0;}

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

你可能感兴趣的文章