首页 > ACM题库 > HDU-杭电 > hdu 2089 不要62-动态规划-[解题报告]C++
2013
12-29

hdu 2089 不要62-动态规划-[解题报告]C++

不要62

问题描述 :

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

输入:

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

输出:

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

样例输入:

1 100
0 0

样例输出:

80

hdu 2089

基础数位dp 用dp[i][j] 表示滴i个数时以j结尾所应该统计的个数 明显每次递推的时候特殊考虑 4 和 6  2 但是在统计的时候需要注意前面是否有4 和62 来防止计算了。第一个数位

#include<cstdio>
#include<cstring>
#define M 10
int dp[M][M];
using namespace std;
void init(){
    dp[0][0]=1;
    for(int i=0;i<M;i++){
        for(int j=0;j<M;j++){
            for(int k=0;k<M;k++){
                if(j==4||k==4) continue;
                if(j==2&&k==6) continue;
                dp[i+1][k]+=dp[i][j];
            }
        }
    }
}
int w[M];
int f(int n){
    if(n==0) return 0;
    int len=0;
    while(n){
        w[++len]=n%10;
        n/=10;
    }
    int tsum=0;
    int flag=0;
    for(int i=len;i>=1;i--){
        for(int j=0;j<w[i];j++){
            if(j==4) continue;
            if(flag==1&&j==2) continue;
            tsum+=dp[i][j];
        }
        if(flag&&w[i]==2) break;
        if(w[i]==4) break;
        if(w[i]==6) flag=1;
        else flag=0;
    }
    return tsum;
}
int main(){
    init();
    int a,b;
    while(~scanf("%d%d",&a,&b)&&(a+b)){
        int ans1=f(b+1)-f(a);
        printf("%d\n",ans1);
    }
    return 0;
}

解题转自:http://blog.csdn.net/wintowanti/article/details/11595115


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  3. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  4. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

  5. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。