HDU 3652 B-number（数位DP）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3652
这道题中‘1’和‘3’相邻很好解决，一个pre即可。但是能被13整除比较难弄。
可以设一个参数cnt记录余数，每次枚举，变成（10*cnt+i），然后%一下13，当pos=0时判断即可。
AC代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 typedef long long ll; 7 ll dp[15][10][13][2]; 8 int a[15]; 9 ll n; 10 ll DFS(int pos,int pre,int limit,int ok,int cnt){ 11 if(pos==0) return ok&&!cnt; 12 if(!limit&&dp[pos][pre][cnt][ok]!=-1) return dp[pos][pre][cnt][ok]; 13 int up=limit?a[pos]:9; 14 ll ans=0; 15 for(int i=0;i<=up;i++){ 16 if(pre==1&&i==3) ans+=DFS(pos-1,i,limit&&i==a[pos],1,(cnt*10+i)%13); 17 else ans+=DFS(pos-1,i,limit&&i==a[pos],ok,(cnt*10+i)%13); 18 } 19 if(!limit) dp[pos][pre][cnt][ok]=ans; 20 return ans; 21 } 22 ll solve(ll x){ 23 int len=0; 24 while(x){ 25 a[++len]=x%10; 26 x/=10; 27 } 28 return DFS(len,0,1,0,0); 29 } 30 int main(){ 31 memset(dp,-1,sizeof(dp)); 32 while(~scanf("%lld",&n)) printf("%lld ",solve(n)); 33 return 0; 34 }