数位dp模板

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3555

代码

#include<bits/stdc++.h>
using namespace std;

#define ll long long
int dat[20];
ll dp[20][2];

ll DFS(int len, bool lead, bool limit) {
	if (len < 0)return 1;
	if (!limit&&dp[len][lead])return dp[len][lead];

	ll sum = 0, up = limit ? dat[len] : 9;
	for (int i = 0; i <= up; i++) {
		if (lead&&i == 9)continue;
		sum += DFS(len-1,i==4,limit&&i==up);
	}

	if (!limit)dp[len][lead] = sum;
	return sum;
}

ll solve(ll num) {
	int cnt = 0;
	while (num) {
		dat[cnt] = num % 10;
		num /= 10;
		cnt++;
	}
	return DFS(cnt-1,false,true);
}
int main() {
	ios::sync_with_stdio(false);
	int t; cin >> t;

	memset(dp,0,sizeof(dp));
	while (t--) {
		ll n; cin >> n;
		cout << n + 1 - solve(n) << endl;
	}

	return 0;
}

题目二：http://acm.hdu.edu.cn/showproblem.php?pid=2089

代码：

#include<bits/stdc++.h>
using namespace std;

#define ll long long
int dat[20];
int dp[20][2];

int DFS(int len, bool lead, bool limit) {
	if (len < 0)return 1;
	if (!limit&&dp[len][lead])return dp[len][lead];

	int sum = 0, up = limit ? dat[len] : 9;
	for (int i = 0; i <= up; i++) {
		if (lead&&i == 2)continue;
		if (i == 4)continue;
		sum += DFS(len-1,i==6,limit&&i==up);
	}

	if (!limit)dp[len][lead] = sum;
	return sum;
}

int solve(int num) {
	int cnt = 0;
	while (num) {
		dat[cnt] = num % 10;
		num /= 10;
		cnt++;
	}
	return DFS(cnt-1,false,true);
}
int main() {
	
	memset(dp,0,sizeof(dp));
	int n, m;
	while (scanf("%d%d",&n,&m)==2&&n+m) {
		cout << solve(m)-solve(n-1) << endl;
	}

	return 0;
}