D - Bomb————數位dp

題目連接配接

會有很多做法，本菜渣現在隻會這一種，如果你有什麼好的做法請留下連結。 本菜渣也會持續更新

//帶記憶數組

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
int a[30];
long long dp[30][2][2][2];//下标 數位 four nine limit
long long dfs(int pos,int four,int nine, int limit)
{

    if( nine&&four&&pos== -1)return 1;//隻有 前面有49才統計數
    else if(pos == -1)
    {
        return 0;
    }


    if(dp[pos][four][nine][limit]!= -1)return dp[pos][four][nine][limit];

    long long re = 0;



    int up;//上限
    up = limit?a[pos]:9;//判斷上限為哪個



    for(int i = 0;i <= up;i++)//循環該位可能出現的數
    {
        if(four&&nine)re+= dfs(pos-1, true,true, limit&&a[pos] == i);//如果之前出現49 後面的數不管是什麼 都符合題意
        else if(four)//上一個是4的情況
        {
            if(i == 9)re+=dfs(pos-1, true,true, limit&&a[pos] == i);//如果上一個是4這一個是9 後面不管是什麼肯定符合題意
            else re+=dfs(pos-1, i == 4,false, limit&&a[pos] == i);// 否則 就重新判斷 判斷該數是否是4
        }
        else //上一個不是4的情況
        {
            re+=dfs(pos-1, i==4,false ,limit&&a[pos] == i);//重新判斷該數是否是4
        }

    }



    return dp[pos][four][nine][limit] = re;
}

long long solve(long long x)//拆分函數
{
    memset(dp , -1, sizeof(dp));
    int len = 0;
    while(x)
    {
        int m = x%10;
        x/=10;
        a[len++] = m;
    }
    return dfs(len-1, false,false, true);


}
int main()
{

    int n;
    cin>>n;
    while(n--)
    {
        ll m;
        scanf("%lld", &m);
        cout<<solve(m)<<endl;
    }
    return 0;
}