hdu2089(数位DP 递推形式)

不要62

Time Limit: 1/1 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 25802    Accepted Submission(s): 8967


Problem Description
杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer)。
杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如:
62315 73418 88914
都属于不吉利号码。但是,61152虽然含有6和2,但不是62连号,所以不属于不吉利数字之列。
你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新的士车上牌照了。
 

 

Input
输入的都是整数对n、m(0<n≤m<1),如果遇到都是0的整数对,则输入结束。
 

 

Output
对于每个整数对,输出一个不含有不吉利数字的统计个数,该数值占一行位置。
 

 

Sample Input
1 100 0 0
 

 

Sample Output
80
 

 

Author
qianneng
 

 

Source
 

 

Recommend
lcy
数位DP
递推形式写法理解:
假设对于一个长度为len的数来说,举个例子来说吧,这个数是78589,len=5,
从高位开始,7这一位,我们可以从0枚举到6,后面没有限制,但是如果当前为枚举到7,那么后面的位数就会有限制,怎么办呢?,、
注意到它有一个特性,就是所有数都是以7开头的,我们可以充分利用以7开头的所有数的前缀都是7这一特性,
所以我们如果去掉这一位(好像有些计数问题上,就是利用去掉某个位置上的数,或者都减去相同的数,方案数相同),
这次我们利用去掉前缀的方案数跟这些数含不吉利的数的方案数是相等的,当然了这个问题并不能直接把前缀去掉就完了,
还得考虑到前缀对当前位的影响,如果是62(加个标记,后面的数就全加上)
,或者如果前缀是6(并且这一位大于2)的情况,就不仅要加上dp[i-1][0]*a[i],还要加上dp[i][1](这样可以形成62这个不吉利数)
具体问题,具体对待嘛。
所以我们可以这样计算,(之前好像哪次的省赛,有道DP,就是只要看数字,数个数的的方式,想清楚了,问题就迎刃而解了,好像也是
计算以某个位置开头的所有的方案数,还是以某个位置结尾的所有的方案数,就可以了)。
a:算出分别以0,1,2,3,4,5,6开头的五位数的含有不吉利数(4和62)的数的个数,这个好弄。
b:算7开头的五位数的数的个数,就要算出分别以70,71,72,73,74,75,76,77开头的五位数的个数
,那么我们具体实现的时候,只要算出以0,1,2,3,4,5,6,7,开头的四位数的个数就行,因为前缀都是7。
c:算78开头的五位数的含有不吉利数的数的个数,就要算出分别以780,781,782,783,784开头的五位数的个数
,那么我们具体实现的时候,只要算出以0,1,2,3,4,开头的三位数的个数就行,因为前缀都是78。
d:算785开头的五位数的含有不吉利的数的个数,就要算出分别以7850,7851,7852,7853,7854,7855,7856,7857
开头的五位数的个数,那么我们具体实现的时候,只要算出以0,1,2,3,4,5,6,开头的2位数的个数就行,因为前缀都是785,
e:算7858开头的五位数的含有不吉利数的数的个数,就要算出分别以78580,78581,78582,78583,78584,78585,78586,78587,78588开头的
五位数的个数,那么我们具体实现的时候,只要算出以0,1,2,3,4,5,6,7,8开头的一位数的个数,因为前缀都是7858.
我们没有算78589,因为不能算以9为前缀的数的个数,len已经减到0,所以传参的时候n需要加1。
可能还会有一个疑问就是说,62,062,0062,不是重复计算可嘛,其实不是因为位数都是固定的,都是五位,所以都要补成5位,
如果62出现在低两位,那么其实算的是62,如果算的是高两位,那么其实算的是62————,62后面会有三个不确定的数字.
 
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std ;
int dp[15][3];
//dp[len][0]代表不含4或62的个数
//dp[len][1]代表不含4或62的个数,首位为2
//dp[len][2]代表含4或62的个数
void init()
{
    memset(dp,0,sizeof(dp));
    //dp[1][0]=9;
    //dp[1][1]=1;
    //dp[1][2]=1;
    dp[0][0]=1;
    for(int len=1;len<=9;len++)
    {
        dp[len][0]=dp[len-1][0]*9-dp[len-1][1];////在最高位加上除了4之外的9个数字,但是可能在2之前加了6  
        dp[len][1]=dp[len-1][0];  //就是在原先不含4或62的最高位加2  
        dp[len][2]=10*dp[len-1][2]+dp[len-1][1]+dp[len-1][0];
//在已经有不吉利数字最高位加任意数字,或者在无吉利数字前加4,或者在2前面加4 } }
int solve(int x) { int s[10],len=0,xx=x; while(x>0) { s[++len]=x%10; x/=10; } s[len+1]=0; //初始化前缀为0,0是没有任何影响的,后面一位可能会用到前面一位 // cout<<len<<endl; int ans=0,flag=0; for(int i=len;i>=1;i--) { ans+=(s[i]*dp[i-1][2]); if(flag) //如果前缀中有出现4或者62的话,那么后面的数就全加上 { ans+=s[i]*dp[i-1][0]; } //只考虑以len位置为i的开头的数 if(!flag && s[i]>4) ans+=dp[i-1][0]; if(!flag && s[i]>6) ans+=dp[i-1][1];//因为是大于号,所以低一位可以完全枚举 //考虑前缀的影响 if(!flag && s[i+1]==6 && s[i]>2) ans+=dp[i][1]; if(s[i]==4 (s[i+1]==6 && s[i]==2) ) { flag=1; } } return xx-ans; } int main() { init() ; int n,m ; // while(scanf("%d%d",&n,&m)) { if(n==0 && m==0) break ; // solve(101); printf("%d\n",solve(m+1)-solve(n)) ;//用[0,m]-[0,n)即可得到区间[n,m] } return 0 ; }

 

dfs写法理解:

dp[len][0]代表首位不为6,剩余长度为len,不含4和62的数的个数,

dp[len][1]代表首位为6,剩余长度为len,不含4和62的数的个数。

同样是枚举每个位置上的数,但是不同的是对于枚举当当前位置最大值的处理,dfs通过fp(代表是否是n的前缀)

这个参数只是用来告诉下一个状态是枚举到9,还是枚举到自身位置的最大值,如果是前缀就只能枚举当自身位置的最大值,

不是就可以从0枚举到9.还有一个参数是用来前缀的最后一位是否为6的状态,

不为6,ret+=dp[len-1][0],

为6,ret+=dp[len][1];

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define LL  long long
LL dp[30][2];
int digit[30];

LL dfs(int len,bool state,bool fp)
{
    if(!len)
        return 1;
    if(!fp && dp[len][state] != -1)  //如果不是前缀,并且已经被计算过
        return dp[len][state];
    //是前缀的话,说明dp[len][state]不能用,就得重新搜索(枚举)。
    LL ret = 0 ;int  fpmax = fp ? digit[len] : 9;
    for(int i=0;i<=fpmax;i++) //分别算出以i开头的数的方案数,
        //62,062,0062,因为位数是固定的,假设是m位,那么都不足m位,后面肯定有东西
    {
        if(i==4  state && i == 2)
            continue;
        //i如果不是6的话,ret+=dp[len][0],如果是6的话,ret+=dp[len][1]
        ret += dfs(len-1,i == 6,fp && i == fpmax);
        //第二个参数来保存前缀的最后一位是否为6的状态,如果为6,下一位就不能为2,否则没有限制
        //第三个参数表明是否是前缀,如果是前缀,下一位就只能枚举到最大值,否则就没有限制
    }
    if(!fp)  //如果是前缀,当前得到的ret的值,就不能代表dp[len][state]的值
        dp[len][state] = ret;
    return ret; //ret代表0到n不含4和62的个数
}

LL f(LL n)
{
    int len = 0;
    while(n)
    {
        digit[++len] = n % 10;
        n /= 10;
    }
    return dfs(len,false,true);
}

int main()
{
    //freopen("test.txt","r",stdin);
    LL a,b;
    memset(dp,-1,sizeof(dp));
     while(cin>>a>>b)
     {
         if(a==0 && b==0)
            break;
          cout<<f(b)-f(a-1)<<endl;
     }

    return 0;
}

比较这两种方式的异同点,递推是利用具有相同前缀的数含4或62的方案数,跟去掉前缀之后的方案数相等这一特性,

而dfs是利用记录是否为前缀这一状态,搜索时,来判断每一位枚举的范围.记忆化搜索得到答案.

更多相关文章
  • 0x01前言 Tor是“The onion router”的简写,Tor项目是诞生于美国军方,被美国海军研究实验室和电子前沿基金会赞助过,现在的开发和维护是Tor项目团队.Tor主要是用来隐藏网络身份,因此执法和情报机构特别关注,并且特别想攻破Tor网络. 在国外研究员的博客,提供了几种攻击思路,每 ...
  • 各位您好,今天我将开始给大家分享微软最新的SCCM 2012系列文章,让大家逐步了解在企业内如何搭建SCCM 2012的同时,了解各个功能模块,对应自己的企业环境来看,那些功能是您现在所需要的.当然还可以看看SCCM 2012比之前的SCCM 2007有什么的变化和改进.我们先从基础开始,从服务器准 ...
  • Quantum注入剖析 Quantum注入攻击是一种“情报窃取”技术,最初由斯诺登披露的文档曝光. 这种技术典型攻击方案就是“HTML重定向”攻击,说简单点就是往受害者流量里注入恶意内容.攻击者在受害者的TCP会话注入了恶意代码,比如可持续追踪的cookie,就可以精确监控这个受害者.一旦确定某段s ...
  • 1.分区要求 1)/:必须有的 2)swap:可选,一般为物理内存的1.5倍,当物理内存大于16G,选择8-16G即可 3)/boot:用来存放内核文件,一般100~200M即可,内核文件不超过100M 划分了分区之后,再格式化,格式化的目的是为了创建文件系统(文件系统可以理解为:组织文件的一种机制 ...
  • 作者:思索 整理:南海 下一页 数据库设计的基本方法     数据库设计是建立数据库及其应用系统的核心和基础,它要求对于指定的应用环境,构造出较优的数据库模式,建立起数据库应用系统,并使系统能有效地存储数据,满足用户的各种应用需求.一般按照规范化的设计方法,常将数据库设计分为若干阶段: 系统规划阶段 ...
  •   来源:网易科技 文/顾晓波 “免费榜要出事.”一名开发者在朋友圈写道.这个时候苹果中国区免费榜正被各大刷榜公司血洗. 5月3日起,一贯被刷榜公司包办的苹果中国区免费榜出现了一个怪现象,Gameloft.Gamevil.Disney.Zynga等公司的游戏齐刷刷地冲上了免费榜TOP 50,这并不是 ...
一周排行
  • 声明:此文转载自博客开发团队的博客,尊重原创工作.该文适合学分布式系统之前,作为背景介绍来读. 谈到分布式系统,就不得不提Google的三驾马车:Google FS[1],MapReduce[2],Bigtable[ ...
  • admin/edit_languages.php   elseif ($_REQUEST['act'] == 'edit') { /* 语言项的路径 */ $lang_file = isset($_POST['fil ...
  • 已知数据文件IN.DAT中存有300个4位数,并已调用读函数readDat()把这些数存入数组a中,请编制一函数jsValue(),其功能是:求出千位数上的数加百位数上的数等于十位数上的数加个位数上的数的个数cnt, ...
  •  基本要求 1.具有计算机的基础知识.2.了解操作系统的基本概念,掌握常用操作系统的使用.3.掌握基本数据结构和常用算法,熟悉算法描述工具--流程图的使用.4.能熟练地使用一种高级语言或数据库语言编写程序.调试程序. ...
  • 优点: 1. 允许模块化程序设计.2.可维护性高,只需创建存储过程一次并将其存储在数据库中,以后即可在程序中调用该过程任意次.存储过程可独立于程序源代码而单独修改,而不需要更改.测试以及重新部署程序集.3.运行速度快 ...
  • Given a BST, transform it into greater sum tree where each node contains sum of all nodes greater than that ...
  • 全网通手机已经成为现在智能手机市场的一个趋势,用户们的需求也越来越大.那么一加2代有全网通版吗?下面小编就为大家介绍一加2代网络制式,来看看吧 在7月28日一加手机即将发布,相信很多人都对这款新机充满了期待.最新消息 ...
  • 天天酷跑贡献币怎么获得 贡献币快速入手方法介绍.一起跟随小编过来看看吧 天天酷跑贡献币怎么获得,快速入手方法详解.随着俱乐部版本的正式上线,一种新的货币贡献币正式进入玩家眼帘,作为俱乐部商店唯一承认的购买货币.没有它 ...
  • 在U3D界面上 选中相应的脚本,重新导入即可
  •   USB  最主要的的是要理解   USB主机发送命令给设备,设备要对主机的命令进行响应, USB通讯的基本单位为 "包"   理解好"包"这个概念是学习USB的关键所在. ...