1586:【 例 2】数字游戏

首页 > 1586:【 例 2】数字游戏 > 列表

1586:【 例 2】数字游戏

1586:【 例 2】数字游戏

时间限制: 1000 ms 内存限制: 524288 KB
提交数: 748 通过数: 413
【题目描述】
科协里最近很流行数字游戏。某人命名了一种不降数,这种数字必须满足从左到右各位数字成小于等于的关系,如 123,446。现在大家决定玩一个游戏,指定一个整数闭区间 [a,b],问这个区间内有多少个不降数。

【输入】
有多组测试数据。每组只含两个数字 a,b,意义如题目描述。

【输出】
每行给出一个测试数据的答案,即 [a,b] 之间有多少不降数。

【输入样例】
1 9
1 19
【输出样例】
9
18
【提示】
数据范围与提示:

对于全部数据,1≤a≤b≤231?1。

提交 统计信息 提交记录

代码:

#includebits/stdc++.h
#define maxn 15
#define ll long long 
using namespace std;

ll dp[maxn][maxn],lim[maxn];
ll x,y;
vectorint v;

ll dfs(ll cur,ll state,int done)
{
	if(cur==-1) return 1;
	if(~(dp[cur][state])!done) return dp[cur][state];
	
	ll end=donelim[cur+1]:9;
	ll res=0;
	for(int i=state;i=end;i++)
	{
		res+=dfs(cur-1,i,done(i==end));
	}
	if(!done) dp[cur][state]=res;
	return res;
	
}

ll work(ll x)
{
	memset(dp,-1,sizeof(dp));
	memset(lim,0,sizeof(lim));
	v.clear();
	ll cnt=0;
	while(x0)
	{
		lim[++cnt]=x%10;
//		v.push_back(x%10);
		x/=10;
	}
	
	ll ans=0;
//	for(int i=0;i=lim[cnt];i++) ans+=_f(cnt,i,)
//	coutcnt'\n';
//	coutv.size()'\n';
	return dfs(cnt,0,1);
	
}

int main()
{
	while(cinxy)
	{
		printf("%lld\n",work(y)-work(x-1));
	}
	
	return 0;
}