HDU 3555 0 Bomb (数位DP)

HDU 3555 0 Bomb (数位DP)

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

3
1
50
500

Sample Output

0
1
15

http://blog.csdn.net/sr_19930829/article/details/38444255
题意就是求从整数1到N中有多少个含有“49”的数？ 比如N=500，那么  "49","149","249","349","449","490","491","492","493","494","495","496","497","498","499",
so the answer is 15.

先说一下总体思路：

假设统计N=591时，那么按以下的顺序进行统计：

1~499         确定5这一位，统计的数比它小

500~589     确定9这一位 ，统计的数比它小

590            确定1这一位，统计的数比它小 

最后判断一下自身是不是符合 即591

循环三次就把符合题意的数的总数全都求出来了，这就是本题的数位DP的奥妙之处.

dp[i][j] 表示长度为i的数（也就是有i位数）状态为j的数的总数有多少

本题状态有三种： 

①dp[i][0]代表长度为i且不包含49的数有多少个

②dp[i][1]代表长度为i且不包含49且左边第一位（最高位）为9的数有多少个

③dp[i][2]代表长度为i且包含49的数有多少个

打表预处理，0<=i<=21（21位就够了）,主要是处理状态的转移

dp[i][0]=dp[i-1][0]*10-dp[i-1][1];                              //dp[i][0]高位随便加一个数字都可以，但是会出现49XXX的情况，要减去
dp[i][1]=dp[i-1][0];                                                     //在不含49的情况下高位加9
dp[i][2]=dp[i-1][2]*10+dp[i-1][1];                            //在含有49的情况下高位随便加一位或者不含49但高位是9，在前面最高位加上4就可以了

http://blog.csdn.net/sr_19930829/article/details/38444255

1. void init()  
2. {  
3.     dp[0][0]=1,dp[0][1]=0,dp[0][2]=0;  
4.     for(int i=1;i<=21;i++)  
5.     {  
6.         dp[i][0]=dp[i-1][0]*10-dp[i-1][1];//dp[i][0]高位随便加一个数字都可以，但是会出现49XXX的情况，要减去  
7.         dp[i][1]=dp[i-1][0];//在不含49的情况下高位加9  
8.         dp[i][2]=dp[i-1][2]*10+dp[i-1][1];//在含有49的情况下高位随便一位或者不含49但高位是9，在前面最高位加上4就可以了  
9.     }  
10. }  
11.   
12. long long cal(long long n)  
13. {  
14.     int len=0;  
15.     while(n)  
16.     {  
17.         bit[++len]=n%10;  
18.         n/=10;  
19.     }  
20.     long long ans=0;  
21.     bit[len+1]=0;  
22.     bool has=false;  
23.     for(int i=len;i>=1;i--)//每次确定一位  
24.     {  
25.         ans+=dp[i-1][2]*bit[i];//低位中含有49，高位随便一个1,2,3....bit[i]都可以，bit[i]是代表有几个数字，比如bit[i]=5,那么代表有五个数字，0,1,2,3,4，比5小。  
26.         if(!has)  
27.         {  
28.             if(bit[i]>4)  
29.                 ans+=dp[i-1][1];//低位中高位是9，前面加上4就可以了  
30.         }  
31.         else  
32.             ans+=(dp[i-1][0])*bit[i];//如果有49，就随便选了，比如 495的时候，有490 491 492 493 494  
33.             //上面这句话困扰了我一天多的时间。为什么不写（d[i-1][0]+dp[i-1][2]）*bit[i]呢，前面已经出现过49  
34.             //那么低位任意选择都可以，dp[i-1][0]是那些低位不出现49的，dp[i-1][2]是那些低位出现49的，按理说应该  
35.             //加上啊，BUT！！！清注意循环里面的第一句ans+=dp[i-1][2]*bit[i]; 前面已经加上了dp[i-1][2]低位有  
36.             //49的情况了，哎，欲哭无泪........  
37.         if(bit[i+1]==4&&bit[i]==9)  
38.            has=true;  
39.     }  
40.     if(has)  
41.         ans++;  
42.     return ans;  
43. }  
44.   
45. //以491为例，先求出所有比400小的数中有多少符合题意的，然后4这一位确定以后，再求所有比490小，再求出所有比491小  
46. //i=3 求出数 049 149 249 349  
47. //i=2 求出数 449  
48. //i=1 求出数 490  
49.   
50. //自身包含49 所以求出数491  
51.   
52. int main()  
53. {  
54.     init();  
55.     int t;cin>>t;  
56.     while(t--)  
57.     {  
58.         cin>>n;  
59.         cout<<cal(n)<<endl;  
60.     }  
61.     return 0;  
62. }  

Read full article from Problem - 3555