不要 62
题意: 给定区间, 求在这个区间中有多少个数字, 不包含 4 且不包含 62;
这道题作为数位 DP 的入门题;
暴力也是可以过
- #include<cstdio>
- #include <iostream>
- #include <cstring>
- #include <string>
- #include <algorithm>
- using namespace std;
- const int maxn =1e6+7;
- int a[maxn];
- bool check(int x)
- {
- while(x>0)
- {
- if(x%10==4)return true;
- if(x%100==62)return true;
- x/=10;
- }
- return false;
- }
- int main(){
- int sum = 0;
- for(int i=1;i<=1000000;i++)
- {
- if(check(i)){a[i]=sum;continue;}
- sum++;
- a[i]=sum;
- }
- int l,r;
- while(~scanf("%d%d",&l,&r)&&l+r)
- {
- printf("%d\n",a[r]-a[l-1]);
- }
- return 0;
- }
当然数位 DP 更快, 利用记忆化 DFS
- #include <iostream>
- #include <cstring>
- #include <string>
- #include <algorithm>
- #include <cstdio>
- using namespace std;
- int dp[10][3],digit[10];
- int dfs(int pos,bool pre_6,bool limit)
- {
- if(pos==0)return 1;
- if(!limit&&dp[pos][pre_6]>=0)return dp[pos][pre_6];
- int ans=0,num=limit?digit[pos]:9;
- for(int i=0;i<=num;i++)
- {
- if(i==4||(pre_6&&i==2))
- continue;
- ans += dfs(pos-1,i==6,limit&&i==num); // 只有之前有限制现在的达到了上限才能构成限制
- }
- return limit?ans:dp[pos][pre_6] = ans;// 如果有限制, 那么就不能记忆化, 否则记忆的是个错误的数.
- }
- int solve(int x)
- {
- int len = 0;
- while(x>0)
- {
- digit[++len]=x%10; // 将数字存在 digit 数组中
- x/=10;
- }
- return dfs(len,false,true);
- }
- int main(){
- memset(dp,-1,sizeof(dp));
- int l,r;
- while(scanf("%d%d",&l,&r),l+r)
- {
- printf("%d\n",solve(r)-solve(l-1));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2506923.html