hdu 3555 bomb 数位dp

╰+哭是因爲堅強的太久メ 2022-08-13 17:58 162阅读 0赞

基础数位dp，作为入门题目；

题意很明确，找出1-n范围内不含49的数字。n的范围为1~n^63-1.

dp\[i\]\[0\]长度为i的数不含49的数的个数

dp\[i\]\[1\]长度为i的数最高位为9的数的个数

dp\[i\]\[2\]长度为i的数含49的数的个数

以下解决时，对n+1，但是没有统计n+1，不过注意可能越界.....

#include <iostream>
    
    using namespace std;
    typedef long long LL;
    
    LL dp[20][3],num[20];
    void initi(){
    	dp[0][0]=1;dp[0][1]=0;dp[0][2]=0;
    	for(int i=1;i<20;++i){
    		dp[i][0]=10*dp[i-1][0]-dp[i-1][1];
    		dp[i][1]=dp[i-1][0];
    		dp[i][2]=10*dp[i-1][2]+dp[i-1][1];
    	}
    }
    	
    
    LL solve(LL x){
    	int len=0;LL tmp=x;
          	while(x){
    		num[++len]=x%10;
    		x/=10;
    	}
    	num[len+1]=0;
    	LL ans=0,flag=0;
    	for(int i=len;i>0;--i){
    		ans+=num[i]*dp[i-1][2];
    		if(flag)ans+=num[i]*dp[i-1][0];
    		if(!flag&&num[i]>4)ans+=dp[i-1][1];
    		if(num[i+1]==4&&num[i]==9)flag=1;
    	}
    	return ans;
    }
    int main(){
        initi();
    	LL x,T;
    	cin>>T;
    	while(T--){
    	   cin>>x;
    	   cout<<solve(x+1)<<endl;
    	}
    	return 0;
    }

递归写法

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    typedef long long LL;
    const int N = 20;
    int dig[N];
    LL dp[N][10][2];
    
    LL dfs(int pos,int pre,int istrue,int limit) { 
        if (pos < 0) return istrue;
        if (!limit && dp[pos][pre][istrue] != -1)
            return dp[pos][pre][istrue];
        int last = limit ? dig[pos] : 9;
        LL ret = 0;
        for (int i = 0; i <= last; i++) { 
            ret += dfs(pos-1,i,istrue || (pre == 4 && i == 9),limit && (i == last));
        }
        if (!limit) { 
            dp[pos][pre][istrue] = ret;
        }
        return ret;
    }
    LL solve(LL n) { 
        int len = 0;
        while (n) { 
            dig[len++] = n % 10;
            n /= 10;
        }
        return dfs(len-1,0,0,1);
    }
    int main(){ 
        memset(dp,-1,sizeof(dp));
        int T;
        //freopen("bomb_in.txt","r",stdin);
        scanf("%d",&T);
        while (T--) { 
            LL n;
            cin>>n;
            cout<<solve(n)<<endl;
        }
        return 0;
    }