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,这并不是 ...
一周排行
  • 易网科技专栏作家 苏一壹挺了这么久,消息还是来了:黑莓(BlackBerry)在8月12日宣布停牌暂停股票交易.黑莓最大股东Fairfax Financial公司董事长兼CEO瓦特萨(Prem Wats)表示将辞职, ...
  • 易网财经7月3日讯 近日小米盒子盗版乐视被判赔偿一事备受关注,今天乐视网网站事业群运营总裁高飞向易网财经表示,小米公司对于败诉的回应是避重就轻,"小米本来是值得尊敬的对手,败诉之后应当坦然面对,承担相应责任 ...
  • 易网科技讯 近日,京东宣布,京东微店已完成升级测试,与京东商城(JD.com)系统实现全面打通,开始大规模招商工作.第三方商家只需提供QQ号和微信ID即可方便入驻京东微店,通过京东商家后台对商品.订单.结算.售后进行 ...
  • 编辑strings.xml的时候 在行<string name="myurl">http://code.dd.com/rr?q=%rr.55</string> 提示下面的错 ...
  •  前两天不小心和csdn做一个专访,地址如下:http://www.csdn.net/article/8/2815824 为此引来一些网友热议. 为此,我特意在此用极简的手法再次解读一下这句话.希望 ...
  • mysql5插入乱码问题   在数据库由4.2升级到5.1.6-comm...之后 都是latin1的默认编码, 以前的程序插入中文乱码 ,以前的写法:在source中加入charset=gb2312,然后在插入前执 ...
  • 学友资料:http://www.cnblogs.com/NeilLing/p/4263267.html 天气查询车联网API http://developer.baidu.com/map/index.php?titl ...
  • 苹果在与三星的专利战中获得了一次重大胜利.美国当地时间周二,加州圣何塞地区法官露西·科赫裁定,初步禁止三星Galaxy Tab 10.1平板电脑在美国销售.露西·科赫在禁令中写道,虽然三星的销量将因此而蒙受损失,但鉴 ...
  • 犯人戴上GPS脚拷后,将时刻被警察监控. 在"GPS监狱"中,给罪犯戴上的就不是手拷了. "大多数人发现使用这种装置与蹲大狱比起来有太多好处了,而且我们又可以因此每天节省45到55美元的 ...
  • SparkInterpreter.java  这个文件里面读取master的属性有些问题:原来代码中"master"属性的获取的地方应该是错了.设置和读取这个属性的对象不是同一个如下修改后从新编译 ...