Bomb Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others) Total Submission(s): 6471 Accepted Submission(s): 2250 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.
我的第一個數位DP。。。動態規劃真強大，前輩們的思想讓我歎服。。由衷的說:佩服！！！
對於這樣一類問題:在某個數字區間內求滿足條件或不滿足條件的數字的個數。 如果問題的數字范圍太大的話，一般來說就是數位DP。
數位DP，我的理解就是 假設求的是n---0之間的滿足條件的數字的個數，假設n=4891,那麼可以這樣算:
1)求出3999---0的滿足條件數字的個數。
2)求出4799---4000的滿足條件數字的個數。
3)求出4889---4800的滿足條件數字的個數。
4)求出4891---4890的滿足條件數字的個數。
以上加起來就是本題答案。
那麼怎麼DP呢？ 有這樣一種思想，如果知道0--k位數字中滿足條件的個數num，那麼0--k+1位數字中滿足條件的個數num1=num*10;因為第k+1位有0--9 10中情況。
以上基本上就是數位dp的思想了。下面解這道題：
題意：給一個數字n，求出0---n之間含有49的數字的個數。
設dp[i][0],dp[i][1],dp[i][2]分別為從0到i位數字之間不含49數字個數，不含49但是最高位(第i位)數字為9的數字的個數,含49的數字的個數。
那麼有 dp[i][0]=dp[i-1][0]*10-dp[i-1][1]; //第i位數字可能是4，所以減去i-1位到0中最高位是9的個數。
dp[i][1]=dp[i-1][0];
dp[i][2]=dp[i-1][2]*10+dp[i-1][1]; //第i位數字可能是4，所以加上i-1位到0中最高位是9的個數。
以上就是主要思想，寫本題需要注意細節,詳見代碼:
1 #include <stdio.h>
2 #include <algorithm>
3 #include <string.h>
4 #include <iostream>
5 using namespace std;
6
7 main()
8 {
9 __int64 n, dp[33][4], ans;
10 int t, i, j, k, bit[33];
11 memset(dp,0,sizeof(dp));
12 dp[0][0]=1;
13 for(i=1;i<=20;i++) //dp過程
14 {
15 dp[i][0]=dp[i-1][0]*10-dp[i-1][1];
16 dp[i][1]=dp[i-1][0];
17 dp[i][2]=dp[i-1][2]*10+dp[i-1][1];
18 }
19 scanf("%d",&t);
20 while(t--)
21 {
22 scanf("%I64d",&n);
23 k=0;
24 n++; //因為該程序求的是[0,n)半開半閉區間的個數，以防數字n滿足條件，所以n+1
25 while(n) //把n每位數字放進一個數組裡
26 {
27 bit[++k]=n%10;
28 n/=10;
29 }
30 ans=0;
31 bit[k+1]=0;
32 int flag=0;
33 for(i=k;i>=1;i--) //求解過程
34 {
35 ans+=dp[i-1][2]*bit[i];
36 if(flag) ans+=dp[i-1][0]*bit[i]; //如果高位數字中含有49 那麼以後不管是什麼數字都滿足條件
37 if(!flag&&bit[i]>4) ans+=dp[i-1][1]; //如果高位數字鐘不含49 但是第i位大於4，那麼需要加上第i位是4，第i+1位是9的數字
38 if(bit[i+1]==4&&bit[i]==9) flag=1;
39 }
40 printf("%I64d\n",ans);
41 }
42 }
