hdu 3652（数位dp）

题意：求解x,y区间中有13字串并且能出13的数的个数

思路：数位dp+记忆化搜索，dp[i][j][k]表示处理到第i位，mod13的余数为j，且状态为k的数的个数。k=0表示已经出现了串13，k=2表示前一个数字是1，k=1表示剩余状态。最终结果为dp[pos][0][0]pos为数的位数。

View Code

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 int dp[11][15][4],bit[11];
 8 int dfs(int pos,int pre,int mod,bool limit,bool flag){
 9     if(pos<=0)return flag&&(mod==0);
10     if(!limit&&flag&&dp[pos][mod][0]!=-1)return dp[pos][mod][0];
11     if(!limit&&!flag&&pre!=1&&dp[pos][mod][1]!=-1)return dp[pos][mod][1];
12     if(!limit&&!flag&&pre==1&&dp[pos][mod][2]!=-1)return dp[pos][mod][2];
13     int end=limit?bit[pos]:9;
14     int sum=0;
15     for(int i=0;i<=end;i++){
16         sum+=dfs(pos-1,i,(mod*10+i)%13,limit&&(i==end),flag||(i==3&&pre==1));
17     }
18     if(!limit&&flag)dp[pos][mod][0]=sum;
19     if(!limit&&!flag&&pre!=1)dp[pos][mod][1]=sum;
20     if(!limit&&!flag&&pre==1)dp[pos][mod][2]=sum;
21     return sum;
22 }
23 int slove(int n){
24     int pos=0;
25     memset(dp,-1,sizeof(dp));
26     while(n){
27         bit[++pos]=n%10;
28         n/=10;
29     }
30     return dfs(pos,0,0,true,false);
31 }
32 int main(){
33     int n;
34     while(scanf("%d",&n)!=EOF){
35         printf("%d\n",slove(n));
36     }
37     return 0;
38 }