HDU 2089.不要62

189


题目



点击显/隐题目

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


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


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


1 100
0 0


80




题解



数位dp问题,当然这题可以暴力搞掉的,不过还是按照数位dp的写法写

一位一位分析
这道题需要判断62,因此需要记录上一位数字

则有dp[i][j]表示前i位并且上一位为j的合法的数目
dp[i][j] = sum{ dp[i-1][k] } 其中 k 是满足条件的数

对于数位dp,有时候存在一个上限,不需要枚举到所有的数,用一个变量记录当前是否存在上限
如果存在上限,就正常跑,如果不存在上限则可以使用记忆化搜索

代码


点击显/隐代码
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

const int maxn = 10;

int a[maxn];
int dp[maxn][10];

/* 第pos位 前一位状态为 pre 当前是否限制当前位(limit) */
int dfs(int pos, int pre, bool limit) {
    //for (int i = maxn; i >= pos; i--)
    //    printf("\t");
    //printf("dfs(%d,%d,%d,%d)\n", pos, pre, limit);

    if (pos == -1)
        return 1;

    if (limit || dp[pos][pre] == -1) {
        int up = limit ? a[pos] : 9;
        int ans = 0;
        for (int now = 0; now <= up; now++) {
            if (pre == 6 && now == 2)
                continue;
            if (now == 4)
                continue;
            ans += dfs(pos - 1, now, limit && now == a[pos]);
        }
        if (!limit)
            dp[pos][pre] = ans;
        return ans;
    }
    return dp[pos][pre];
}

int solve(int x) {
    int pos = 0;
    while (x) {
        a[pos++] = x % 10;
        x /= 10;
    }
    int ans = dfs(pos - 1, -1, true);
    //printf("solve(%d) = %d\n", x, ans);
    return ans;
}
int main() {
    int l, r;
    while (scanf("%d%d", &l, &r) != EOF) {
        if (l == 0 && r == 0)
            break;
        memset(dp, -1, sizeof(dp));
        printf("%d\n", solve(r) - solve(l - 1));
    }
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论