不要62
Time Limit: 1000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13988Accepted Submission(s): 4491
Problem Description
杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer)。
杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如:
62315 73418 88914
都属于不吉利号码。但是,61152虽然含有6和2,但不是62连号,所以不属于不吉利数字之列。
你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新的士车上牌照了。
Input
输入的都是整数对n、m(0<n≤m<1000000),如果遇到都是0的整数对,则输入结束。
Output
对于每个整数对,输出一个不含有不吉利数字的统计个数,该数值占一行位置。
Sample Input
Sample Output
Author
qianneng
Source
Recommend
lcy
Statistic|
Submit|
Discuss|
Note
第一次做数位dp。
所以就挑一道最简单的来做。
dp[i][j]代表只有i位且第i位为j的符合个数:
#include<stdio.h>
#include<string.h>
int dp[10][12];
int n,m;
int a[10];
int tran(int nn,int aa[])
{
int po = 0;
while(nn)
{
aa[po++] = nn%10;
nn = nn/10;
}
return po-1;
}
int DFS(int len,int ss,int flag,int doing,int ab) //ab代表上一位是否等于6
{
if(len<0)return flag;
if(!doing && dp[len+1][ss]!=-1)
return dp[len+1][ss];
int end = doing?a[len]:9;
int ans = 0;
for(int i=0;i<=end;i++)
{
if(i!=4 && (i!=2 || !ab))
ans+=DFS(len-1,i,flag,doing&&end==i,i==6);
}
if(!doing)dp[len+1][ss] = ans;
return ans;
}
int main()
{
memset(dp,-1,sizeof(dp));
while(scanf("%d%d",&n,&m) && n+m!=0)
{
int alen,mm=0;
alen = tran(n-1,a);
mm+=DFS(alen,0,1,1,0);
alen = tran(m,a);
mm=DFS(alen,0,1,1,0)-mm;
printf("%d\n",mm);
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
自己做的HDU ACM已经AC的题目
hdu动态规划算法集锦
hdu题目分类
HDU图论题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
Hdu 1237 解题代码