ZZUOJ-1196-單調數 （鄭州大學第七屆ACM大學生程序設計競賽D題，DP）

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;
}