样例输出 0 求调
查看原帖
样例输出 0 求调
362750
TernaryTree楼主2022/7/16 09:56
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 21;

int cnt;
int num[maxn];
int dp[maxn][maxn][maxn][maxn][maxn];

int dfs(int cur, int from, int last, bool f4, bool f8, bool lim) {
	if (f4 && f8) return 0;
	if (cur == 0) {
		return last == 3;
	}
	if (!lim && ~dp[cur][from][last][f4][f8]) {
		return dp[cur][from][last][f4][f8];
	}
	int ans = 0;
	int to = (lim ? num[cur] : 9);
	for (int i = (cur == cnt); i <= to; i++) {
		ans += dfs(cur - 1, i, (last == 3 ? 3 : last + from == i), f4 || i == 4, f8 || i == 8, lim && i == to);
	}
	if (!lim) {
		dp[cur][from][last][f4][f8] = ans;
	}
	return ans;
}

int solve(int x) {
	cnt = 0;
	while (x) {
		num[++cnt] = x % 10;
		x /= 10;
	}
	memset(dp, -1, sizeof(dp));
	return dfs(cnt, 0, 0, 0, 0, 1);
}

signed main() {
	int l, r;
	cin >> l >> r;
	cout << solve(r) - solve(l - 1) << endl;
	return 0;
}
2022/7/16 09:56
加载中...