数位 dp
给出一个区间, 求区间里满足某些条件的数有几个
直接暴力求解
打表 + 前缀和
数位 dp
当区间范围很大时, 时间复杂度需要, 无法暴力, 只能用数位 dp 来做
模板求 [1,n] 的数字里不含 49 的个数
数组 \(a[i]\)存放数字 n(即区间的端点值)的值, 如果 n 是 1234, 那么数组就是 {4,3,2,1} 但是 dfs 是从最高位 1 开始的
数组 \(dp[i][j]\)是指当到达第 i 位, 该数字的前缀是 j, 且满足条件的情况的个数
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<string>
- #define ios_fuck iOS::sync_with_stdio(0)
- using namespace std;
- typedef long long ll;
- int a[50];
- ll dp[50][10];
- ll dfs(int pos,int pre,bool limit){//pos 当前在数字的第几位, pre 是当前数字位的前一位, limit 是限制词, 是求枚举所需的最大值时用的
- if(pos == -1) return 1;// 结束
- if(!limit && dp[pos][pre] != -1) return dp[pos][pre];
- ll tmp = 0;
- for(int i = 0; i <= up; i++){
- if(pre == 4 && i == 9)continue;
- // if(i == 4) continue;
- tmp += dfs(pos - 1,i,limit && i == a[pos]);
- }
- if(!limit) dp[pos][pre] = tmp;
- return tmp;
- }
- ll solve(ll x){
- int pos = 0;
- while(x){
- a[pos++] = x % 10;
- x /= 10;
- }
- return dfs(pos-1,0,true);
- }
- int main(){
- ll ri;
- int t;
- scanf("%d",&t);
- memset(dp,-1,sizeof(dp));
- while(t--){
- scanf("%lld",&ri);
- printf("%lld\n",solve(ri));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3382339.html