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 }
?
)
)
)
)
