ZZUOJ-1196-单调数 （郑州大学第七届ACM大学生程序设计竞赛D题，DP）

Description

对于一个正整数x，如果x的每一位都不大于它右边一位上的数字，那么就称x是递增数，例如：112，4557，18899，111。

类似的，如果x的每一位都不小于它右边一位上的数字，那么就称x是递减数，例如：986，6331，77311，111。

递增数和递减数统称单调数。（111既是递增数，也是递减数，所以111肯定是单调数）

Input

有多组输入。

每组输入一个数n。（n<=100)

Output

对于每组输入数据中的n，输出小于10n的单调数个数。

Sample Input

Sample Output

HINT

Source

郑州大学第七届ACM大学生程序设计竞赛

思路：DP

AC代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define LL long long using namespace std; /*dpi[n][m]表示的是第n位添加数字m（0....9）的构成单调递增数个数 dpd[n][m]表示的是第n位添加数字m（0....9）的构成单调递减数个数 */ LL dpi[105][10]; LL 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=1; j<10; j++) { for(int k=j; k<10; k++) dpi[i][j]+=dpi[i-1][k]; for(int k=j; k>=1; k--) dpd[i][j]+=dpd[i-1][k]; dpd[i][j]+=1; //加上10,20，...，90，100,200，...，900,...之类的数 } } } int main() { init(); int n; while(cin>>n) { LL ans = 0; for(int j=1; j<=n; j++) { for(int i=0; i<10; i++) ans+=dpi[j][i]+dpd[j][i]; ans-=9; //减去递增数和递减数重复的数，如11，22，...，99之类的数 } printf("%lld\n", ans); //妈蛋，在oj上，这里不能用%I64d，WA了一次 } return 0; }