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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法修养

POJ-1458 Common Subsequence(线性动规,最长公共子序列问题)

Common Subsequence Time Limit: 1000MS Memory Limit: 10000K Total Submis...

33470
来自专栏ml

hdu----(5045)Contest(数位dp)

Contest Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (J...

36450
来自专栏ml

HDUOJ---3743Frosh Week(BIT+离散化)

Frosh Week Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K...

33490
来自专栏ml

hdu 3038 How Many Answers Are Wrong ( 带 权 并 查 集 )

How Many Answers Are Wrong Time Limit: 2000/1000 MS (Java/Others)    Memory Limi...

37370
来自专栏ml

HDUOJ----Super Jumping! Jumping! Jumping!

Super Jumping! Jumping! Jumping! Time Limit : 2000/1000ms (Java/Other)   Memory ...

28660
来自专栏小樱的经验随笔

2017 Multi-University Training Contest - Team 9 1004&&HDU 6164 Dying Light【数学+模拟】

Dying Light Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/13107...

28550
来自专栏ml

HDUOJ-------2844Coins

Coins Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

30880
来自专栏ml

hdu-------1081To The Max

To The Max Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K...

30060
来自专栏算法修养

POJ 2773 Happy 2006(容斥原理+二分)

Happy 2006 Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 1...

30870
来自专栏ml

2014---多校训练2(ZCC Loves Codefires)

ZCC Loves Codefires Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 3276...

29050

扫码关注云+社区

领取腾讯云代金券