hdu 2089 记忆化搜索写法（数位dp）

/*

记忆化搜索，第二维判断是否是6

*/

#include<stdio.h>

#include<string.h>

#define N 9

int dp[N][2],digit[N];

int dfs(int len,int cnt,int ok) {//cnt代表是否是6，ok代表前一个是当前为最大值，并且当前也是最大值

  if(!len)return 1;

    if(!ok&&dp[len][cnt]!=-1)return dp[len][cnt];

    int i,ans=0,maxx=ok?digit[len]:9;

    for(i=0;i<=maxx;i++) {

        if(i==4||cnt&&i==2)//是否是4，上一个是6当前是2要continue;

           continue;

            ans+=dfs(len-1,i==6,ok&&i==maxx);

    }

    if(!ok)

        dp[len][cnt]=ans;

    return ans;

}

int f(int n) {

 int len=0;

 while(n) {

    digit[++len]=n%10;

    n/=10;

 }

 return dfs(len,0,1);

}

int main() {

   int n,m;

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

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

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

   }

return 0;}

巴特西

hdu 2089 记忆化搜索写法（数位dp）

最新文章

热门文章