80分求调wa#5,#8
查看原帖
80分求调wa#5,#8
1209223
iris_hsd楼主2024/10/30 13:43
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 11;
int f[N][N];

void init()
{
	for(int i = 0;i <= 9;i++) f[1][i] = 1;
	for(int i = 2;i < N;i++)
		for(int j = 0;j <= 9;j++)
			for(int k = 0;k <= 9;k++)
				if(abs(j - k) >= 2) f[i][j] += f[i - 1][k];
}

int dp(int x)
{
	int res = 0, last = -2;
	if(x == 0) return 0;
	vector <int> a;
	while(x)
	{
		a.push_back(x % 10);
		x /= 10;
	}
	int len = a.size() - 1;
	for(int i = len;i >= 0;i--)
	{
		int y = a[i];
		for(int j = (i == len);j < y;j++)
			if(abs(j - last) >= 2) res += f[i + 1][j];
		if(y - last < 2) break;
		last = y;
		if(!i) res++;
	}
	for(int i = 1;i <= len;i++)
		for(int j = 1;j <= 9;j++)
			res += f[i][j];
	return res;
}

signed main()
{
	init();
	int l, r;
	cin >> l >> r;
	cout<<dp(r) - dp(l - 1)<<"\n";
	return 0;
}

2024/10/30 13:43
加载中...