【题意】【1,n】里面还有数字13并且是13的倍数的数字的个数。

【解题方法】数位DP裸题。

dp[l][mod][iso][has] ：l为数字长度，(mod为当前数字对13的取余值，iso为是否存在， has为最后一位是否为数字1。

int dfs(int l,int mod,bool iso,bool has,bool jud) ：jud判断是否为边界值。

【AC 代码】

//Created by just_sort 2016/8/12//All Rights Reserved#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;int digit[11];int dp[11][13][2][2];int dfs(int l,int mod,bool iso,bool has,int jud){ if(l==0) return (!mod&&has); if(!jud&&dp[l][mod][iso][has]!=-1) return dp[l][mod][iso][has]; int nex = jud?digit[l]:9; int ans = 0; for(int i=0; i<=nex; i++){ ans += dfs(l-1,(mod*10+i)%13,i==1,has||(i==3&&iso),i==nex&&jud); } return jud?ans:dp[l][mod][iso][has]=ans;}int f(int num){ int pos=0; while(num){ digit[++pos]=num%10; num/=10; } return dfs(pos,0,0,0,true);}int main(){ int n; memset(dp,-1,sizeof(dp)); while(scanf("%d",&n)!=EOF){ printf("%dn",f(n)); }}

免责声明：文章源自网络，版权归原作者所有，如有侵犯联系删除。