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;
}