hdu---(3555)Bomb(數位dp（入門）)
Bomb
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 7921 Accepted Submission(s): 2778
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
Hint
From 1 to 500, the numbers that include the sub-sequence "49" are "49","149","249","349","449","490","491","492","493","494","495","496","497","498","499", so the answer is 15.
Author
fatboy_cw@WHU
Source
2010 ACM-ICPC Multi-University Training Contest（12）——Host by WHU
題意： 給你一個數n,要你統計出1到n中出現含有49數字的個數： 比如 498,549,49.....
對於這一道題： 看到一個博客引用了這張圖片，覺得說的很清晰，就引用了..
我們對於 i-1長度的數字分析，無疑就這麼集中情況（當然只是圍繞49來說的哇）首部分析：
i-1長度 那麼對於 i長度
首部為49 ，那麼它的格式必然為： 49**** ？49****（？可能為9）
首部保函9 ，那麼它的格式必然為： 9***** ？9*****（？可能為4）
首部部位49 ，那麼它的格式為： ******* ？*******（？可能為9）
我們不妨用dp[i][2]表示首部為49的,dp[i][1]表示首部為9的，dp[i][0]表示首部不為49，於是我們可以發現這樣一個規律：
dp[i-1][2]向前移一位，即原來的個位變為十位，十位變為百位的那種移位。 形成dp[i][2],但是需要注意的是:
當dp[i-1][2]時，其實由我上面說的，？可能為9 ，所以當向前移一位時，？為9的可能性被去掉了。所以
dp[i-1][2]*10（移動一位時）需要減去 開頭為9的那種模式dp[i-1][1],所以得到：
（1） dp[i][2]=dp[i-1][2]*10-dp[i-1][1];
對於i位首部為9那麼後面只需要滿足不為49即可，剛好滿足dp[i][0];
（2） 所以 dp[i][1]=d[i-1][0];
對於首部不為49的
同樣也可以分析出來...
dp[i][0]=dp[i-1][0]*10+dp[i-1][1];
於是得到這樣一個預處理方程：
dp[i][2]=dp[i-1][2]*10-dp[i-1][1];
dp[i][1]=d[i-1][0];
dp[i][0]=dp[i-1][0]*10+dp[i-1][1];
代碼：詳情見代碼：
1 //#define LOCAL
2 #include<cstdio>
3 #include<cstring>
4 #define LL __int64
5 using namespace std;
6 const int maxn=25;
7 LL dp[maxn][3]={0};
8 int nn[maxn];
9 int main()
10 {
11
12 #ifdef LOCAL
13 freopen("test.in","r",stdin);
14 #endif
15 int cas,i;
16 LL n;
17 scanf("%d",&cas);
18 /*數位DP的慣有模式預處理*/
19 dp[0][0]=1;
20 for(i=1;i<=20;i++)
21 {
22 dp[i][0]=dp[i-1][0]*10-dp[i-1][1];
23 dp[i][1]=dp[i-1][0];
24 dp[i][2]=dp[i-1][2]*10+dp[i-1][1];
25 }
26 while(cas--)
27 {
28 scanf("%I64d",&n);
29 i=0;
30 n+=1;
31 memset(nn,0,sizeof(nn));
32 while(n>0)
33 {
34 nn[++i]=n%10;
35 n/=10;
36 }
37 LL ans=0;
38 bool tag=0;
39 int num=0;
40 for( ; i>=1 ; i-- )
41 {
42 ans+=dp[i-1][2]*nn[i]; /*計算49開頭的個數*/
43 if(tag){
44 ans+=dp[i-1][0]*nn[i]; /*當前面出現了49的時候，那麼後面出現的任何數字也要進行統計*/
45 }
46 if(!tag&&nn[i]>4)
47 {
48 ans+=dp[i-1][1]; /*如果沒有出現49開頭，只要首部大於5，那麼必定保函有一個49*/
49 }
50 if(num==4&&nn[i]==9)
51 tag=1;
52 num=nn[i];
53 }
54 printf("%I64d\n",ans);
55 }
56 return 0;
57 }
