P2657求调
  • 板块灌水区
  • 楼主__KevinMZ__
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/14 19:14
  • 上次更新2024/10/14 20:42:56
查看原帖
P2657求调
1358215
__KevinMZ__楼主2024/10/14 19:14
#include<bits/stdc++.h>
using namespace std;
typedef long long l;
l mxi[105];
l dp[105][10];
l dfs(l pos, l pre, bool flag, bool lead)
{
	if(pos <= 0) return 1;
	if(!flag && dp[pos][pre] != -1) return dp[pos][pre];
	int mx = flag ? mxi[pos] : 9, ret = 0;
	for(int i = 0; i <= mx; i++)
	{
		if(lead || abs(pre - i) >= 2)
			ret += dfs(pos - 1, i, flag && (i == mx), lead && (i == 0));
	}
	return !flag ? dp[pos][pre] = ret : ret;
}
l solve(l x)
{
	int pos = 0;
	while(x)
	{
		mxi[++pos] = x % 10;
		x /= 10;
	}
	return dfs(pos, 0, 1, 1);
}
int main()
{
	memset(dp, -1, sizeof(dp));
	l a, b;
	cout << LLONG_MAX << "\n";
	cin >> a >> b;
	cout << solve(b) - solve(a - 1);
	return 0;
} 
2024/10/14 19:14
加载中...