首页 > 代码库 > Hdu3555Bomb数位dp

Hdu3555Bomb数位dp

含有49的 。。就是不要49

。。也可以直接搞

#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>#include<math.h>using namespace std;typedef long long LL;LL dp[100][2];LL up[111];LL dfs(LL now,LL pre,LL flag){    if(now==1) return 1;    if(!flag&&~dp[now][pre]) return dp[now][pre];    LL limit=flag?up[now-1]:9,ret=0;    for(LL i =0 ;i<=limit;i++){        if(i==9&&pre) continue;        ret+=dfs(now-1,i==4,flag&&(limit==i));    }    return flag? ret: dp[now][pre]= ret;}LL solve(LL x){    LL len=0;    while(x){        up[++len]=x%10;        x/=10;    }    return dfs(len+1,0,1);}int  main(){    LL n;    LL Icase;    memset(dp,-1,sizeof(dp));    cin>>Icase;    while(Icase--){        cin>>n;        LL t1=solve(n);        cout<<n-t1+1<<endl;    }    return 0;}