hdu3555 + 2089 (数位dp入门)

悠悠 2022-08-20 14:18 19阅读 0赞

hdu3555

给出数字n，要求1到n范围内所有的数字中出现连续49的数字的个数。n很大。

例如500，那么出现连续49的数字有49,149,249,349,449，490,491,942...499等15个数字。

这道题目就是明显的数位dp入门题目。

我们先预处理一下，dp\[i\]\[j\]表示的是i位数字并且第i位上的数字为j所不含49的个数

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    long long dp[20][10];
    //dp[i][j]表示的是i位数字并且第i位上的数字为j所不含49的个数
    
    void init()
    {
    	memset(dp,0,sizeof(dp));
    	dp[0][0] = 1 ;
    	for(int i = 1 ; i < 20 ; i++)
    	{
    		for(int j=0;j<10;j++)//枚举第i位可能出现的数
    		{
    			for(int k=0;k<10;k++)//枚举第i-1位可能出现的数
    			{
    				if(!(j==4&&k==9))
                    {
                        dp[i][j]+=dp[i-1][k];
                    }
    			}
    		}
    	}
    }
    long long solve(long long n)
    {
    	int digit[20];
    	int len = 0;
    	long long m = n ;
    	while(n)
    	{
    		digit[++len] = n%10;
    		n/=10;
    	}
    	digit[len+1]=0;
    	long long ans = 0;
    	for(int i=len ; i>0 ; i--)
    	{
    		for(int j=0;j<digit[i];j++)   //j为第i位上面的数字
    		{
    			if(!(digit[i+1]==4&&j==9))
    				ans+=dp[i][j];
    		}
    		if(digit[i]==9&&digit[i+1]==4)   //已经有49了，所以直接退出
    			break;
    	}
    	return  m-ans;
    }
    int main()
    {
        init();
        int t ;
        long long n ;
        scanf("%d",&t);
    	while(t--)
    	{
    	    scanf("%I64d",&n);
    		printf("%I64d\n",solve(n+1));
    	}
    	return 0;
    
    }

hdu2089

和上面基本是一个题目的变形，要求的是在一个区间（n,m）里面不出现4并且没有连续62的数字。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    int dp[10][10];
    //dp[i][j]表示的是i位数字并且第i位上的数字为j所不含不吉利数字的数量
    
    void init()
    {
    	memset(dp,0,sizeof(dp));
    	dp[0][0] = 1;
    	for(int i=1;i<=7;i++)
    	{
    		for(int j=0;j<10;j++)//枚举第i位可能出现的数
    		{
    			for(int k=0;k<10;k++)//枚举第i-1位可能出现的数
    			{
    				if(j!=4&&!(j==6&&k==2))
                    {
                        dp[i][j]  += dp[i-1][k];
                    }
    			}
    		}
    	}
    }
    int solve(int n)
    {
    	int digit[10];
    	int len = 0;
    	while(n)
    	{
    		digit[++len] = n%10;
    		n/=10;
    	}
    	digit[len+1]=0;
    	int ans = 0;
    	for(int i=len ; i>0 ; i--)
    	{
    		for(int j=0;j<digit[i];j++)   //j为第i位上面的数字
    		{
    			if(j!=4&&!(digit[i+1]==6&&j==2))
    				ans+=dp[i][j];
    		}
    		if(digit[i]==4||(digit[i]==2&&digit[i+1]==6))
    			break;
    	}
    	return  ans;
    }
    int main()
    {
    	int l,r;
    	init();
    	while(scanf("%d%d",&l,&r)==2)
    	{
    		if(l==0&&r==0) break;
    		else printf("%d\n",solve(r+1)-solve(l));
    	}
    	return 0;
    
    }