数位dp（求1-n中数字1出现的个数）-白红宇

数位dp（求1-n中数字1出现的个数）

阅读量：6981 次

发布时间：2019-06-27

本文共 1358 字，大约阅读时间需要 4 分钟。

题意：求1-n的n个数字中1出现的个数。

解法:数位dp，dp[pre][now][equa] 记录着第pre位为now，equa表示前边是否有降数字（即后边可不能够任意取，true为没降，true为已降）；常规的记忆化搜索

代码：

/******************************************************* author:xiefubao*******************************************************/#pragma comment(linker, "/STACK:102400000,102400000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 //freopen ("in.txt" , "r" , stdin);using namespace std;#define eps 1e-8const double pi=acos(-1.0);typedef long long LL;const int Max=10100;const int INF=1000000007;int fac[10];void init(){ fac[0]=1; fac[1]=1; for(int i=2; i<10; i++) fac[i]=fac[i-1]*10;}char s[20];int dp[20][20][2];int n;int num[20];int dfs(int pre,int now,int equa){ if(pre==0) return now==1; if(dp[pre][now][equa]!=-1) return dp[pre][now][equa]; int ans=0; if(now==1&&!equa) ans+=fac[pre+1]; if(now==1&&equa) ans+=n%fac[pre+1]+1; int en=equa?num[pre-1]:9; for(int i=0;i<=en;i++) ans+=dfs(pre-1,i,equa&&i==num[pre-1]); return dp[pre][now][equa]=ans;}int getans(int t){ int p=0; memset(dp,-1,sizeof dp); while(t) { num[p++]=t%10; t/=10; } int ans=0; for(int i=0; i<=num[p-1]; i++) { ans+=dfs(p-1,i,i==num[p-1]); } return ans;}int main(){ init(); while(cin>>n) { printf("%d\n",getans(n)); } return 0;}