hdu 3652数位dp

/*
数位dp
题意：找到1-n之间包含13这个子串并且能够整除13的数
解：刚开始dp[N][N][2]这里的2用来记录是否为13表示当前位是否为13，我把上一位为1当前位为13和上一位部位1
这种情况在数组中没有记录。
*/
#include<stdio.h>
#include<string.h>
#define N 14
int dp[N][N][3];
int digit[N];
int dfs(int len,int mod,int cnt,int ok) {
 if(!len) {
    if(mod==0&&cnt==2)return 1;
    return 0;
 }
 if(!ok&&dp[len][mod][cnt]!=-1)
    return dp[len][mod][cnt];
 int ans=0,i,maxx=ok?digit[len]:9;
 for(i=0;i<=maxx;i++)  {
     if(cnt==2||(cnt==1&&i==3))
    ans+=dfs(len-1,(mod*10+i)%13,2,ok&&i==maxx);
     else
     if(i==1)//刚开始这里判断条件写成if(cnt==0&&i==1)这样是不对的因为漏掉了一种情况(i==1&&cnt==1)
        ans+=dfs(len-1,(mod*10+i)%13,1,ok&&i==maxx);
 else
      ans+=dfs(len-1,(mod*10+i)%13,0,ok&&i==maxx);
 }
 if(!ok)
    dp[len][mod][cnt]=ans;
 return ans;
}
int f(int n) {
 int len=0;
 while(n) {
     digit[++len]=n%10;
     n/=10;
 }
 return dfs(len,0,0,1);
}
int main() {
  int n;
  memset(dp,-1,sizeof(dp));
  while(scanf("%d",&n)!=EOF) {
    printf("%d\n",f(n));
  }
return 0;}

<pre name="code" class="cpp">/*
我原来的思路，刚开始写的时候少开了一维记录pre的情况
*/
#include<stdio.h>
#include<string.h>
#define N 14
int dp[N][N][2][2];
int digit[N];
int dfs(int len,int mod,int pre,int cnt,int ok) {
 if(!len) {
    if(mod==0&&cnt==1)return 1;
    return 0;
 }
 if(!ok&&dp[len][mod][pre][cnt]!=-1)
    return dp[len][mod][pre][cnt];
 int ans=0,i,maxx=ok?digit[len]:9;
 for(i=0;i<=maxx;i++)  {
        if(cnt||(pre&&i==3))
        ans+=dfs(len-1,(mod*10+i)%13,i==1,1,ok&&i==maxx);
        else
            ans+=dfs(len-1,(mod*10+i)%13,i==1,0,ok&&i==maxx);
 }
 if(!ok)
    dp[len][mod][pre][cnt]=ans;
 return ans;
}
int f(int n) {
 int len=0;
 while(n) {
     digit[++len]=n%10;
     n/=10;
 }
 return dfs(len,0,0,0,1);
}
int main() {
  int n;
  memset(dp,-1,sizeof(dp));
  while(scanf("%d",&n)!=EOF) {
    printf("%d\n",f(n));
  }
return 0;}

hdu 3652数位dp

原文：http://blog.csdn.net/u011483306/article/details/39802655