Codeforces1036C.Classy Numbers(数位DP)

题目链接:Codeforces1036C.Classy Numbers

题意:

定义了一种数叫做:classy number,是指一个数p,对于它的各位,最多只有三个非零数,给定区间[l,r],问区间内有多少个classy number。

题解:

数位dp板子题。

首先考虑第一点,答案满足前缀和性质。然后对于[0,A],我们采用记忆化搜索,用dp(i)(j)表示长度为i的数,非零位数为3-j的数的个数。

参考代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T, num[30], dp[30][5];
ll l, r;
ll dfs(int pos, int cnt, bool limit)
{
    if (pos == 0 && cnt >= 0)
        return 1;
    if (pos <= 0 || cnt < 0)
        return 0;
    if (!limit && dp[pos][cnt])
        return dp[pos][cnt];
    int tot = 0, maxn;
    if (limit)
        maxn = num[pos];
    else
        maxn = 9;
    for (int i = 0; i <= maxn; i++)
        tot += dfs(pos - 1, cnt - min(i, 1), limit && i == maxn);
    if (!limit)
        dp[pos][cnt] = tot;
    return tot;
}
ll sol(ll x)
{
    int len = 0;
    while (x)
    {
        num[++len] = x % 10;
        x /= 10;
    }
    return dfs(len, 3, 1);
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%lld%lld", &l, &r);
        printf("%lld\n", sol(r) - sol(l - 1));
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。