数位DP写挂了求助
查看原帖
数位DP写挂了求助
103226
BeautifulWater楼主2022/7/27 10:37
/*********************************************************************
    程序名:
    版权:
    作者:BeautifulWater&&cc
    日期: 2022-06-13 13:16
    说明:
*********************************************************************/
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define rep(i,x,n) for(register int i=x;i<n;i++)
#define repd(i,x,n) for(register int i=x;i<=n;i++)
#define MAX 1000005
#define MOD 1000000007
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define PII pair<int,int>

template<class T>inline void rd(T &x) {
	x = 0;
	char o, f = 1;
	while (o = getchar(), o < 48)
		if (o == 45)
			f = -f;
	do
		x = (x << 3) + (x << 1) + (o ^ 48);
	while (o = getchar(), o > 47);
	x *= f;
}

template<class T>inline void print(T x, bool op = 1) {
	static int top, stk[105];
	if (x < 0)
		x = -x, putchar('-');
	if (x == 0)
		putchar('0');
	while (x)
		stk[++top] = x % 10, x /= 10;
	while (top)
		putchar(stk[top--] + '0');
	putchar(op ? '\n' : ' ');
}
using namespace std;

const int N = 2E6 + 500;
int n, m, k;
ll l, r;
vector<int > num;
ll f[20][10][10][2][2][2][2];

//f[pos][pre1][pre2][ans][have4][have8][limit]
ll dfs(int pos, int pre1, int pre2, bool ans, bool have4, bool have8, bool limit) {
	if (have4 && have8)
		return 0;

	if (pos < 0) {
		return ans;
	}
	if (f[pos][pre1][pre2][ans][have4][have8][limit] != -1)
		return f[pos][pre1][pre2][ans][have4][have8][limit];
	int up = (limit == 1) ? num[pos] : 9;
	ll tot = 0;
	for (int i = 0; i <= up; i++) {
		bool flag = (i == pre1 && pre1 == pre2);
		tot += dfs(pos - 1, i, pre1, ans || flag, have4 || (i == 4), have8 || (i == 8), limit && (i == up));
	}
	return f[pos][pre1][pre2][ans][have4][have8][limit] = tot;
}

void init() {
	num.clear();
	memset(f, -1, sizeof(f));
}

ll solve(ll x) {
	init();
	if (x < 1e10)
		return 0;
	while (x) {
		num.PB(x % 10);
		//	cout << x % 10 << endl;
		x /= 10;
	}
	int tot = 0;
//	cout << num.back() << endl;
	for (int i = 1; i <= num.back(); i++) {

		//int dfs(int pos, int pre1, int pre2, int pre3, int ans, bool have4, bool have8, bool limit)
		tot += dfs(9, i, 0, 0, i == 4, i == 8, i == num.back());
	}
	return tot;

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	//int T;
	//cin>>T;
	//while(T--)
	cin >> l >> r;
	cout << solve(r) - solve(l - 1);
	return 0;
}

2022/7/27 10:37
加载中...