ZZUOJ1196: 单调数

/*

   注意的事项:是输出小于 10^n的正整数的个数哦！开始的时候总比样例输出多一个数，

   纠结了好久，原来是 0加了进去了！

   dpI[n][m]表示的是第n位添加数字m（0....9）的构成单调递增数个数 

   dpD[n][m]表示的是第n位添加数字m（0....9）的构成单调递减数个数 

*/

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

long long dpI[105][10];

long long dpD[105][10];

void init(){

   for(int i=1; i<10; ++i)

       dpI[1][i]=dpD[1][i]=1;

   for(int i=2; i<=100; ++i){

        for(int j=0; j<10; ++j){

           if(j!=0){//单调递增的数一定没有数字0，因为前边的数字最小为 1 

               for(int k=j; k>=1; --k)

                  dpI[i][j]+=dpI[i-1][k];

           }

           for(int k=j; k<10; ++k){//单调递减的数字中可以有0，但是第二位为0时，第一位不能为0 

                 if(i==2 && k==0) continue;

              dpD[i][j]+=dpD[i-1][k]; 

        }

   }

}

int main(){

   init();

   int n;

   while(cin>>n){

       long long sum=0;

       for(int j=1; j<=n; ++j){

         for(int i=0; i<10; ++i)

           sum+=dpI[j][i]+dpD[j][i];

         sum-=9;

       }

       cout<<sum<<endl;

   return 0;

本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3913685.html，如需转载请自行联系原作者