HDU - 3555-Bomb(数位dp)

63 阅读 0 评论 42 点赞

我是靠谱客的博主怕黑小蘑菇，最近开发中收集的这篇文章主要介绍HDU - 3555-Bomb(数位dp)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接

题意就是如果一个数字里包含49这个子数字(子串…),那么分数+1
问1-N之间能得到多少分数

这个题和不要62基本一样,都是入门数位dp题……
只需要去掉一个条件即可.

这里再简单的说下.

dp[ i ] [ j ]代表该数字的位数为 i ,最高位为 j 时符合条件的有多少个
例如dp[ 2 ] [ 4] =9 (符合条件的数有 40,41,42,43,44,45,46,47,48)

打好表之后,再按照N+1从高位到低位统计出不带49的数字的个数.最后n+1-这个答案即可.

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<iomanip>
#include<algorithm>
#define max(a,b)   (a>b?a:b)
#define min(a,b)   (a<b?a:b)
#define swap(a,b)  (a=a+b,b=a-b,a=a-b)
#define memset(a,v)  memset(a,v,sizeof(a))
#define X (sqrt(5)+1)/2.0  //Wythoff
#define Pi acos(-1)
#define e  2.718281828459045
#define eps 1.0e-8
using namespace std;
typedef long long int LL;
typedef pair<int,int> pa;
const int MAXL(1e5);
const int INF(0x3f3f3f3f);
const int mod(1e9+7);
int dir[4][2]= {{-1,0},{1,0},{0,1},{0,-1}};
LL dp[20][20];
void init()
{
    memset(dp,0);
    dp[0][0]=1;
    for(int i=1; i<=19; i++)
    {
        for(int j=0; j<=9; j++)
        {
            if(j==4)
            {
                for(int k=0; k<=9; k++)
                    if(k!=9)
                        dp[i][j]+=dp[i-1][k];
            }
            else
            {
                for(int k=0; k<=9; k++)
                    dp[i][j]+=dp[i-1][k];
            }

        }
    }
}
int a[20];
LL solve(LL n)
{
    int len=0;
    while(n)
        a[++len]=n%10,n/=10;
    a[len+1]=0;
    LL ans=0;
    for(int i=len;i>=1;i--)
    {
        for(int j=0;j<a[i];j++)
        {
            if(a[i+1]==4&&j==9)
                continue;
            else
                ans+=dp[i][j];
        }
        if(a[i+1]==4&&a[i]==9)
            break;
    }
    return ans;

}
int main()
{
    init();
    cout<<dp[2][4]<<endl;
    int T;
    cin>>T;
    while(T--)
    {
        LL n;
        cin>>n;
        LL temp=solve(n+1);
        cout<<n+1-temp<<endl;
    }

}