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，如需轉載請自行聯系原作者