首页 > 代码库 > HDU 3555 数位DP

HDU 3555 数位DP

2024-07-07 02:59:39   220人阅读

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 }

 


联系
我们