学步园

题意：求1----n(64位整数)内含49的数的个数。

算法：数位dp， 可以用递归dfs或非递归写， 前者效率略低但思路很清晰，代码也很容易写，后者效率略高，但编码复杂度高。

思路：根据自己的需要在dfs传入的参数进行修改或添加，dp记忆化一下没有首位限制的并且自己需要的情况。

递归：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
int a[34];
ll dp[34][3];
/*  0 含49
 *  1 不含49，但以9结尾
 *  2 不含49
 */
ll dfs(int len, int pre, bool has, bool lim) {
	if(!len) return has;
	if(!lim) {
		if(!has && pre!=4 && ~dp[len][0]) return dp[len][0];
		if(!has && pre==4 && ~dp[len][1]) return dp[len][1];
		if(has && ~dp[len][2]) return dp[len][2];
	}
	ll ret = 0;
	int m = lim ? a[len] : 9;
	for(int i = 0; i <= m; i++)
		ret += dfs(len-1, i, has|(pre==4&&i==9), lim&&i==m);
	if(!lim) {
		if(!has && pre!=4) dp[len][0] = ret;
		if(!has && pre==4) dp[len][1] = ret;
		if(has) dp[len][2] =ret;
	}
	return ret;
}
ll gao(ll n) {
	int len = 0;
	while(n) {
		a[++len] = n%10;
		n/=10;
	}
	return dfs(len, 0, 0, 1);
}
int main() {
	int i, j, cas; ll n;
	memset(dp, -1, sizeof(dp));
	cin >> cas;
	while(cas--) {
		cin >> n;
		cout << gao(n) << endl;
	}
	return 0;
}

非递归：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL __int64
LL n;
/*
 * 0 不含49
 * 1 9开头不含49
 * 2 含49
 */
LL dp[22][3];
void init() {
	int i, j, k;
	dp[0][0] = 1;
	for(i = 0; i < 20; i++) {
		dp[i+1][0] = dp[i][0]*10 - dp[i][1];
		dp[i+1][1] = dp[i][0];
		dp[i+1][2] = dp[i][2]*10 + dp[i][1];
	}
}
LL gao(LL n) {
	int a[22], len = 0;
	while(n) { a[len++] = n%10; n /= 10; }
	LL ans = 0;
	int i, j;
	bool flag = 0;
	for(i = len-1; i >= 0; i--) {
		for(j = 0; j < a[i]; j++) {
			ans += dp[i][2];
			if(flag) ans += dp[i][0];
		}
		if(!flag) {
			if(a[i] > 4) ans += dp[i][1];
		}
		if(a[i+1] == 4 && a[i] == 9) flag = 1;
	}
	if(flag) ans++;
	return ans;
}
int main() {
	int i, j, cas;
	cin >> cas;
	init();
	while(cas--) {
		cin >> n;
		cout << gao(n) << endl;
	}
	return 0;
}