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
",f(n));
  }
return 0;}