p2657 windy数-白红宇

p2657 windy数

阅读量：6070 次

发布时间：2019-06-20

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

分析

首先这是一个询问一段区间内的个数的问题，所以我们可以用差分的思想用sum(R)-sum(L-1)。然后我们考虑如何求出sum(n)，我们用dp[i][j][k][t]表示考虑到第i位，最后一个数是j，是否已经小于n和是否已经考虑完前导零。至于转移和一般的套路一样，详见代码。注意最后记得考虑n自己。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;long long a[20],dp[20][11][2][2];inline long long go(long long n){ if(!n)return 0; long long m=n,i,j,k,cnt=0; long long h=10,lo=1; while(1){ if(m
                   
                    =lo)break; h*=10,lo*=10; } while(lo){ a[++cnt]=m/lo; m%=lo; lo/=10; } memset(dp,0,sizeof(dp)); dp[0][0][0][0]=1; a[0]=0; for(i=1;i<=cnt;i++){ for(j=0;j<=a[i];j++){ k=a[i-1]; if(abs(j-k)>=2){ if(j
                    
                     =2){ dp[i][j][1][1]+=dp[i-1][k][1][1]; } if(!k){ if(j)dp[i][j][1][1]+=dp[i-1][k][1][0]; else dp[i][j][1][0]+=dp[i-1][k][1][0]; } } } } long long ans=dp[cnt][a[cnt]][0][1]; for(i=0;i<=9;i++) ans+=dp[cnt][i][1][1]; return ans;}int main(){ long long a,b; scanf("%lld%lld",&a,&b); cout<
                     
                      <

转载于:https://www.cnblogs.com/yzxverygood/p/9491662.html

你可能感兴趣的文章