hdoj2089（入门数位dp）

题目链接：https://vjudge.net/problem/HDU-2089

题意：给定一段区间求出该区间中不含4且不含连续的62的数的个数。

思路：这周开始做数位dp专题，给自己加油^_^，一直觉得数位dp很牛逼哈哈，个人觉得这位巨佬讲得特别好：https://blog.csdn.net/wust_zzwh/article/details/52100392，超适合初学者。这题似乎是数位dp入门题，也是我第一道数位dp题哈哈。其中有个优化就是将memset放在while循环之外，因为dp保存的信息即dp[pos][sta]:长度为pos+1，上一位为6或不为6的满足题意的数的个数，该性质是所有数共有的，与输入无关，所以一直可以保存。

AC代码：

#include<cstdio>

#include<cstring>

using namespace std;

int a[],dp[][],n,m;

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

    if(pos==-) return ;

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

    int up=limit?a[pos]:;

    int tmp=;

    for(int i=;i<=up;++i){

        if(i==) continue;

        if(pre==&&i==) continue;

        tmp+=dfs(pos-,i,i==,limit&&a[pos]==i);

    }

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

    return tmp;

}

int solve(int x){

    int pos=;

    while(x){

        a[pos++]=x%;

        x/=;

    }

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

}

int main(){

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

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

        printf("%d\n",solve(m)-solve(n-));

    }

    return ;

}

巴特西

hdoj2089（入门数位dp）

最新文章

热门文章