HDU3652 B-number（数位DP）题解

思路：

这里的状态分为3种，无13和末尾的1，无13且末尾为1，有13，然后DFS

等我搞清楚数位DP就来更新Orz

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<queue>

#include<set>

#include<vector>

#include<map>

#include<stack>

#include<cmath>

#include<algorithm>

#define ll long long

using namespace std;

const int N = 1000000000+5;

int dp[12][15][3],a[20];    //dp[pos][mod][status] //status:0无13和末尾1，1末尾为1，2有13

int dfs(int pos,int mod,int sta,bool limit){

    if(pos == -1) return mod == 0 && sta == 2;

    if(!limit && dp[pos][mod][sta] != -1)   return dp[pos][mod][sta];

    int top = limit? a[pos] : 9;

    int sta2;

    ll ret = 0;

    for(int i = 0;i <= top;i++){

        sta2 = sta;

        if(sta == 0 && i == 1) sta2 = 1;

        else if(sta2 == 1 && i == 3) sta2 = 2;

        else if(sta2 == 1 && i != 1) sta2 = 0;

        ret += dfs(pos-1,(mod*10+i)%13,sta2,limit && i == top);

    }

    if(!limit) dp[pos][mod][sta] = ret;

    return ret;

}

ll solve(int x){

    int pos = 0;

    while(x){

        a[pos++] = x % 10;

        x /= 10;

    }

    return dfs(pos-1,0,0,true);

}

int main(){

    int n;

    memset(dp,-1,sizeof(dp));

    while(~scanf("%d",&n)){

        printf("%lld\n",solve(n));

    }

    return 0;

}

巴特西

HDU3652 B-number（数位DP）题解

最新文章

热门文章