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 ++i)

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

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

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

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

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

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

 for(int k=j; k ++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 ++j){

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

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

 sum-=9;

 cout sum endl;

 return 0;

}