hdu 3555（位dp)

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

题目大意是让你求出[1，n]中多少个数包含49；

1.dp[len][0] 代表数字长度为len不含49的个数

2.dp[len][1] 代表数字长度为len不含49但是以9开头的个数（显然dp[len][1]包含在dp[len][0]中）

3.dp[len][2] 代表数字长度为len含有49的个数

View Code

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 __int64 dp[22][3];
 5 int digit[22];
 6 
 7 void Initiate(){
 8     dp[0][0]=1;
 9     for(int i=1;i<21;i++){
10         dp[i][0]=10*dp[i-1][0]-dp[i-1][1];  // 在dp[i-1][0]前面添上0~9,但是要减去dp[i-1][1] 因为4和9构成49 
11         dp[i][1]=dp[i-1][0];  // 直接在dp[i-1][0]前面添上9就行了 
12         dp[i][2]=10*dp[i-1][2]+dp[i-1][1]; // 在dp[i-1][2]前面添上0~9,或者在dp[i-1][1]前面添上4 
13     }
14 }
15 
16 
17 int main(){
18     int _case;
19     scanf("%d",&_case);
20     Initiate();
21     while(_case--){
22         __int64 n;
23         scanf("%I64d",&n);
24         memset(digit,0,sizeof(digit));
25         int len=1;
26         while(n){
27             digit[len++]=n%10;
28             n/=10;
29         }
30         bool flag=false;
31         __int64 ans=0;
32         for(int i=len-1;i>=1;i--){
33             ans+=dp[i-1][2]*digit[i];
34             if(flag){
35                 ans+=dp[i-1][0]*digit[i];
36             }else if(digit[i]>4){
37                 ans+=dp[i-1][1];
38             }
39             if(digit[i+1]==4&&digit[i]==9){
40                 flag=true;
41             }
42         }
43         //推出循环时如果flag==true,则ans++,以为此时末两位正好是49
44         if(flag)
45             ans++;
46         printf("%I64d\n",ans);
47     }
48     return 0;
49 }