学步园

找出1 - N中所有包含49字串的数字个数

思路：普通的数位DP，先找出布包含的，然后总数减去不包含的即可

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 25;

int t;
char num[N];
ll dp[N][10], ans;

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%s", num);
		int n = strlen(num);
		sscanf(num, "%I64d", &ans);
		ans++;
		int pre = 0, flag = 0;
		memset(dp, 0, sizeof(dp));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 10; j++) {
				for (int k = 0; k < 10; k++) {
					if (j == 9 && k == 4) continue;
					dp[i + 1][j] += dp[i][k];
				}
			}
			if (flag) continue;
			for (int j = 0; j < num[i] - '0'; j++) {
				if (j == 9 && pre == 4) continue;
				dp[i + 1][j]++;
			}
			if (pre == 4 && num[i] - '0' == 9) flag = 1;
			pre = num[i] - '0';
		}
		for (int i = 0; i < 10; i++) ans -= dp[n][i];
		ans -= !flag;
		printf("%I64d\n", ans);
	}
	return 0;
}