首页 > 代码库 > hdu 3555（数位dp 入门）

hdu 3555（数位dp 入门）

2024-07-19 09:30:57   212人阅读

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

Bomb

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 7716    Accepted Submission(s): 2702


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
参考：http://blog.csdn.net/ecjtu_yuweiwei/article/details/11835209
 
  1. /* 
  2. 题意：求1~N中含有数字49的个数     1 <= N <= 2^63-1 
  3. 方法：数位DP 
  4. dp[len][0] 代表长度为len不含49的方案数 
  5. dp[len][1] 代表长度为len不含49但是以9开头的数字的方案数 
  6. dp[len][2] 代表长度为len含有49的方案数 
  7. 状态转移如下 
  8. dp[i][0] = dp[i-1][0] * 10 - dp[i-1][1];  //如果不含49且，在前面可以填上0-9 但是要减去dp[i-1][1] 因为4会和9构成49 
  9. dp[i][1] = dp[i-1][0];  //这个直接在不含49的数上填个9就行了 
  10. dp[i][2] = dp[i-1][2] * 10 + dp[i-1][1]; //已经含有49的数可以填0-9，或者9开头的填4 
  11. 写完动态转移方程后就把N从高位到低位一个一个统计了 
  12. 在统计到某一位的时候，加上 dp[i-1][2] * digit[i] 是显然没问题，这是因为这一位可以填【0，(digit[i]-1)】这个区间的数 
  13. 若这一位之前挨着49，那么加上 dp[i-1][0] * digit[i] 也是显然OK。 
  14. 若这一位之前没有挨着49，但是digit[i]比4大，那么当这一位填比digit[i]小的4的时候，就得加上dp[i-1][1]（以9开头的数字的方案数） 
  15.  
  16. */  
        PS：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <cstdio>
#include <cmath>
typedef long long ll;
using namespace std;
ll dp[22][4];
ll digit[22];

void sove()
{
        dp[0][0]=1;
        for(int i=1;i<21;i++)
        {
          dp[i][0]=dp[i-1][0]*10-dp[i-1][1];
          dp[i][1]=dp[i-1][0];
          dp[i][2]=dp[i-1][2]*10+dp[i-1][1];
        }
}


int main()
{
        ll  T,n;
        cin>>T;
        sove();
        while(T--)
        {
            scanf("%I64d",&n);
            memset(digit,0,sizeof(digit));
            int len=0;
            while(n)
            {
             digit[++len]=n%10;
             n/=10;
            }
            int flag=0,last=0;
            ll cnt=0;
            for(int i=len;i>=1;i--)
            {
                cnt+=dp[i-1][2]*digit[i];

                if(flag)
                        cnt+=dp[i-1][0]*digit[i];
                if(!flag&&digit[i]>4)
                        cnt+=dp[i-1][1];
                if(last==4&&digit[i]==9)
                        flag=1;
                last=digit[i];
            }
            if(flag)cnt++;
            printf("%I64d\n",cnt);
        }
  return 0;
}

hdu 3555（数位dp 入门）


联系
我们