HDU 3555 Bomb（数位DP）

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

和不要62那道题一样，如果处理有‘49’的不好处理，那么就把不含‘49’的都求出来，然后$x-solve(x)+1$即可。

注意这里的加1：在处理不含‘49’中，数位dp会处理到0的情况，而题目则要求从1开始。

AC代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 typedef long long ll;
 6 ll dp[50][50];
 7 int a[50];
 8 ll DFS(int pos,int pre,int limit){
 9     if(pos==0) return 1;
10     if(limit==0&&dp[pos][pre]!=-1) return dp[pos][pre];
11     int up=limit?a[pos]:9;
12     ll ans=0;
13     for(int i=0;i<=up;i++){
14         if(pre==4&&i==9) continue;
15         ans+=DFS(pos-1,i,limit&&i==a[pos]);
16     }
17     if(limit==0) dp[pos][pre]=ans;
18     return ans;
19 }
20 ll solve(ll x){
21     int len=0;
22     ll t=x;
23     while(x){
24         a[++len]=x%10;
25         x/=10;
26     }
27     return t-DFS(len,0,1)+1;
28 }
29 int main(){
30     int T;
31     ll x;
32     scanf("%d",&T);
33     memset(dp,-1,sizeof(dp));
34     while(T--){
35         scanf("%lld",&x);
36         printf("%lld
",solve(x));
37     }
38     return 0;
39 }

AC代码