题目传送门:Problem - 3555 (hdu.edu.cn)
题目大意
给定一个N,求[1, N]范围内的数字转换形成的字符串中包含"49"的数字。 (1 <= N <= 2^63-1)
思路
因为数据太大了,所以直接前缀和肯定行不通,所以需要数位dp。
典型的数位dp模板题。
代码
#include <bits/stdc++.h> #define int long long using namespace std; int a[20]; int dp[20][20]; int dfs(int pos, int pre, bool limit) //得到不含有49的数字个数 { if(pos == 0)return 1; if(!limit && dp[pos][pre] != -1)return dp[pos][pre]; //!limit保证不被限制,防止出现状态冲突 int res = 0, up = limit ? a[pos] : 9; for(int i = 0;i <= up; ++ i) { if(pre == 4 && i == 9)continue; //如果遇到了49这个数字就跳过 res += dfs(pos - 1, i, limit && i == a[pos]); } if(!limit)dp[pos][pre] = res; //保存和读取dp的信息都需要保证!limit return res; } int solve(int N) //得到[0, N]之间不含有49的数字个数 { int k = 0; while(N)a[++ k] = N % 10, N /= 10; return dfs(k, 0, 1); } signed main() { memset(dp, -1, sizeof dp); int T;cin >> T; while(T --) { int N;cin >> N; printf("%lld\n", N + 1 - solve(N)); } return 0; }
Comments NOTHING