洛谷P2602 [ZJOI2010]数字计数

洛谷P2602 [ZJOI2010]数字计数

原题链接

数位dp

这也是一道比较基础的数位dp题。

有一点需要注意，需要加上前导0的判断，否则在统计0的个数时会多余统计很多数

直接看代码吧（有注释）

不会真的有人写数位dp不用深搜吧，不会吧，不会吧

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long

using namespace std;

ll l, r, len;
ll num[15], dp[13][13][2][2];	//dp[len][sum][flag][lim]

ll dfs(ll len, ll now, ll sum, ll flag, ll lim){	//len：当前处理到x的第几位，now：当前在查找数字几的个数，sum：当前数字出现了几次，flag：前导0判断（1：是 0：否），lim：上界判断（1：有 0：无）
	if(!len) return sum;	//处理完了，返回sum
	if(dp[len][sum][flag][lim] != -1) return dp[len][sum][flag][lim];	//记忆化
	ll res = lim ? num[len] : 9;
	ll ans = 0;
	for(ll i = 0; i <= res; i++)
		ans += dfs(len - 1, now, sum + (!(flag && (!i)) && (i == now)), flag && (!i), lim && (i == res));		//这个sum传递好好看看，要判断是否是前导0
	return dp[len][sum][flag][lim] = ans;
}

ll solve(ll x, ll now){
	len = 0;
	while(x){
		num[++len] = x % 10;	//这里是倒着存x的每一位的
		x /= 10;
	}
	memset(dp, -1, sizeof(dp));	//dp数组还是-1
	return dfs(len, now, 0, 1, 1);
}

signed main(){
	scanf("%lld%lld", &l, &r);
	for(ll i = 0; i <= 9; i++)
		printf("%lld ",solve(r, i) - solve(l - 1, i));	//前缀和思想统计答案
	printf("
");
	return 0;
}

完结撒花~