[HDU4734] 不要62（数位dp入门）

题意：统计区间 [a,b] 中不含 4 和 62 的数字有多少个。

思路：数位dp

就是数位上不能有4也不能有连续的62，没有4的话在枚举的时候判断一下，不枚举4就可以保证状态合法了，所以这个约束没有记忆化的必要，而对于62的话，涉及到两位，当前一位是6或者不是6这两种不同情况我计数是不相同的，所以要用状态来记录不同的方案数。
dp[pos][sta]表示当前第pos位，前一位是否是6的状态，这里sta只需要去0和1两种状态就可以了，不是6的情况可视为同种，不会影响计数。

Code

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int a[20];

int dp[20][2];

int dfs(int pos, int pre, int sta, int limit){

    if (pos==0) return 1;

    if (!limit&&dp[pos][sta]!=-1) return dp[pos][sta];

    int up = limit?a[pos]:9;

    int tmp = 0;

    for (int i = 0; i <= up; i++) {

        if (pre==6&&i==2) continue;

        if (i==4) continue;

        tmp += dfs(pos-1, i, i==6, limit&&i==a[pos]);

    }

    if(!limit) dp[pos][sta] = tmp;

    return tmp;

}

int solve(int x) {

    int pos = 1;

    while (x){

        a[pos++] = x%10;

        x /= 10;

    }

    return dfs(pos-1, -1, 0, 1);

} 

int main()

{

    int l, r;

    memset(dp, -1, sizeof(dp));

    while (~scanf("%d%d", &l, &r)&&l+r)

        printf("%d\n", solve(r)-solve(l-1));

    return 0;

}

巴特西

[HDU4734] 不要62（数位dp入门）

最新文章

热门文章