1 /* 2    注意的事项:是输出小于 10^n的正整数的个数哦！开始的时候总比样例输出多一个数， 3    纠结了好久，原来是 0加了进去了！ 4     5    dpI[n][m]表示的是第n位添加数字m（0....9）的构成单调递增数个数  6    dpD[n][m]表示的是第n位添加数字m（0....9）的构成单调递减数个数  7 */ 8 #include<iostream> 9 #include<cstring>10 #include<cstdio>11 #include<algorithm>12 using namespace std;13 14 long long dpI[105][10];15 long long dpD[105][10];16 17 void init(){18    for(int i=1; i<10; ++i)19        dpI[1][i]=dpD[1][i]=1;20    for(int i=2; i<=100; ++i){21         for(int j=0; j<10; ++j){22            if(j!=0){//单调递增的数一定没有数字0，因为前边的数字最小为 1 23                for(int k=j; k>=1; --k)24                   dpI[i][j]+=dpI[i-1][k];25            }26        27            for(int k=j; k<10; ++k){//单调递减的数字中可以有0，但是第二位为0时，第一位不能为0 28                  if(i==2 && k==0) continue;29               dpD[i][j]+=dpD[i-1][k]; 30            }31         }32    }33 }34 35 int main(){36    init();37    int n;38    while(cin>>n){39        long long sum=0;40        for(int j=1; j<=n; ++j){41          for(int i=0; i<10; ++i)42            sum+=dpI[j][i]+dpD[j][i];43          sum-=9;44        }45        cout<<sum<<endl;46    }47    return 0;48 }