找顺数【数位dp】

输出1到n中含有6的数的个数。

样例输入

样例输出

找规律感觉好难想（好像是什么100以内有19个，200以内有19*2个，600以内115个，700以内214个...,1000以内有271，2000以内有2*271个），就直接套数位dp的模板了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int dp[20][3];
 6 int digit[20];
 7 
 8 int dfs(int pos,int sta,bool limit)
 9 {
10     if(pos==0) return sta==1;
11     if(!limit&&dp[pos][sta]!=-1)
12         return dp[pos][sta];
13     int ans=0;
14     int up=limit?digit[pos]:9;
15     for(int i=0;i<=up;i++){
16         int nsta=0;
17         if(sta||i==6) nsta=1;
18     ans+=dfs(pos-1,nsta,limit&&i==up);
19     }
20     if(!limit) return dp[pos][sta]=ans;
21     return ans;
22 }
23 
24 int solve(int x)
25 {
26     int len=0;
27     while(x){
28         digit[++len]=x%10;
29         x/=10;
30     }
31     return dfs(len,0,true);
32 }
33 
34 int main()
35 {
36     int n;
37     memset(dp,-1,sizeof(dp));
38     while(scanf("%d",&n)==1)
39     {
40         printf("%d
",solve(n));
41     }
42     return 0;
43 }