HDU 2089 – 不要62 [数位DP]

Link

传送门

Problem

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

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

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

Analysis

跟网上一大神学的,记忆化搜索,比直接递推清晰多了,而且貌似速度快了不少。

dp[i][j]中,i表示还剩下i位,j表示最后一位是不是6,dp[i][j]即合法情况数。

从高位到低位,依此枚举当前位的可取状态。代码中fp表示first place。详细请看代码。

Code

#include <bits/stdc++.h>
using namespace std;

int dp[10][3], num[10];

int dfs(int len, bool state, bool fp) {
    if(len < 1) return 1;
    if(!fp && dp[len][state] != -1)
        return dp[len][state];
    int maxv = fp ? num[len] : 9;
    int ans = 0;
    for(int i = 0; i <= maxv; ++i) {
        if(i == 4 || (state && (i == 2)))
            continue;
        ans += dfs(len-1, i == 6, fp && i == maxv);
    }
    if(!fp) dp[len][state] = ans;
    return ans;
}

int solve(int n) {
    memset(dp, -1, sizeof(dp));
    memset(num, 0, sizeof(num));
    int cnt = 0;
    while(n) {
        num[++cnt] = n % 10;
        n /= 10;
    }
    return dfs(cnt, false, true);
}

int main() {
    int n, m;
    while(scanf("%d%d", &n, &m), n || m) {
        printf("%d\n", solve(m) - solve(n-1));
    }
    return 0;
}

欢迎留言