CDOJ--1404

原题链接：http://acm.uestc.edu.cn/problem.php?pid=1404

分析：定义dp[i][j]表示i位时最左边为j时的情况，那么dp[i][[j]可以由dp[i-1][k](k>=j)得到。

Non-Decreasing Digits

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define maxn 100005
#define ll long long
using namespace std;
ll dp[70][12];
void solve()
{
	for(int i=0;i<=9;i++)dp[1][i]=1;
	for(int i=2;i<=64;i++)
	{
		ll sum=0;
		for(int j=9;j>=0;j--)
		{
			dp[i][j]=sum+dp[i-1][j];
			sum+=dp[i-1][j];
		}
	}
}
int main()
{
	int P;
	solve();
	scanf("%d",&P);
	while(P--)
	{
		int cas,n;
		scanf("%d%d",&cas,&n);
		ll ans=0;
		for(int i=0;i<=9;i++)
		ans+=dp[n][i];
		printf("%d %lld
",cas,ans);
	}
	return 0;
}