HDU-2089不要62-暴力或数位DP入门
2024-10-06 09:58:55
不要62
题意:给定区间,求在这个区间中有多少个数字,不包含4且不包含62;
这道题作为数位DP的入门题;
暴力也是可以过
#include<cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std; const int maxn =1e6+;
int a[maxn];
bool check(int x)
{
while(x>)
{
if(x%==)return true;
if(x%==)return true;
x/=;
}
return false;
}
int main(){
int sum = ;
for(int i=;i<=;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-]);
} return ;
}
当然数位DP更快,利用记忆化DFS
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>
using namespace std; int dp[][],digit[];
int dfs(int pos,bool pre_6,bool limit)
{
if(pos==)return ;
if(!limit&&dp[pos][pre_6]>=)return dp[pos][pre_6];
int ans=,num=limit?digit[pos]:;
for(int i=;i<=num;i++)
{
if(i==||(pre_6&&i==))
continue;
ans += dfs(pos-,i==,limit&&i==num); //只有之前有限制现在的达到了上限才能构成限制
}
return limit?ans:dp[pos][pre_6] = ans;//如果有限制,那么就不能记忆化,否则记忆的是个错误的数. }
int solve(int x)
{
int len = ;
while(x>)
{
digit[++len]=x%; //将数字存在digit数组中
x/=;
}
return dfs(len,false,true);
} int main(){
memset(dp,-,sizeof(dp));
int l,r;
while(scanf("%d%d",&l,&r),l+r)
{
printf("%d\n",solve(r)-solve(l-));
}
return ;
}
最新文章
- External Configuration Store Pattern 外部配置存储模式
- 时间管理的若干Tips
- JAZZ
- ashx
- PHP面向对象的标准
- jquery操作cookie {分享}
- 第二百九十六天 how can I 坚持
- phpcms v9和discuz X3.1实现同步登陆退出论坛(已实现)
- 14-C语言宏
- 简述.jpg .Gif .png-8 .png-24的区别
- 第十六次 ccf 201903-2 二十四点
- 关于Oracle重新启动
- Codeforces 633F The Chocolate Spree 树形dp
- JS膏集01
- bash执行命令分别输出正常日志和错误日志
- applyColorMap()研究(如果我对现有的colormap不满意,那么如何具体来做)
- redis的高级事务CAS(乐观锁)
- SQL Server 2012 books
- hadoop学习笔记(四):hdfs常用命令
- jmeter3.3—插件管理器的安装