萌新不会 dp 求助数位 dp
查看原帖
萌新不会 dp 求助数位 dp
298549
SIXIANG32楼主2022/8/4 13:01

RT

hack:1 100

但是不会调啊/ll

//SIXIANG
#include <iostream>
#include <cstring>
#define MAXN 100000
#define QWQ cout << "QWQ" << endl;
using namespace std;
int f[20][114514][2][2], arr[20], tot = 0;
int digit(int i, int sum, int limit, int lead, int num) {
	if(!i) return sum;
	if(f[i][sum][limit][lead] != -1) return f[i][sum][limit][lead]; 
	int lim = ((lim) ? (arr[i]) : 9), rest = 0;
	for(int p = 0; p <= lim; p++)
		rest += digit(i - 1, sum + ((p || (!lead)) && (p == num)), (limit && (p == arr[i])), (lead && (!p)), num);
	f[i][sum][limit][lead] = rest;	
	return rest;
}
int solve(int x, int num) {
	memset(f, -1, sizeof(f));
	memset(arr, 0, sizeof(arr));
	tot = 0;
	int tmp = x;
	do {
		arr[++tot] = x % 10;
		x /= 10;
	} while(x);
	return digit(tot, 0, 1, 1, num);
}
int main() {
	int l, r; cin >> l >> r;
	for(int p = 0; p <= 9; p++) {
		cout << solve(r, p) - solve(l - 1, p) << ' ';
	}
}
2022/8/4 13:01
加载中...