boj 32

dp，k位的以i∈[0,9]开头的no-decreasing Num的个数为

dp[k][i]=dp[k-1][i]+dp[k-1][i+1]+...+dp[k-1][9],

对于输入的n

只需输出dp[n+1][0]即可

#include<iostream>
using namespace std;

#define N 66
long long dp[N][10];

int main()
{
	for(int i=0;i<=9;i++)
		dp[1][i]=1;
	for(int i=2;i<N;i++)
	{
		for(int j=0;j<=9;j++)
		{
			for(int k=j;k<=9;k++)
				dp[i][j]+=dp[i-1][k];
		}
	}
	int p;
	scanf("%d",&p);
	while(p--)
	{
		int num,n;
		scanf("%d%d",&num,&n);
		printf("%d %lld\n",num,dp[n+1][0]);
	}
}