题解 CF1036C 【Classy Numbers】

· · 题解

算法：裸数位dp

一般地，数位dp可以用来解决下面的问题： 给定一个结果为bool类型的函数f(x)，求[L,R]内有多少个数满足f(x)是真。其中一般L,R<=1e7或更大，且f(x)与数位相关。

本题中，用dp[i][j]代表考虑前i个数位，当前i位中有j个非零数位时，有多少个数满足条件。

这样我们就很容易处理[1,pow(10,t)]中的答案。

现在假设我们需要求[1,3812]的答案。当我们从第一位开始dfs时，从0遍历到3（最高位最大为3），如果第一位是0或1或2，则后面的数据无需考虑限制，都可以从0遍历到9。如果第一位是3，则第二位最大是8。我们使用数组上界变量代表这个限制，如果变量为0代表这一位无需考虑限制，否则代表这一位需要考虑限制。

具体注释见代码。

#include <iostream>
#include <cstring>
using namespace std;

typedef long long ll;//数位dp的题目一般都需要long long

ll a[20]; //代表当前处理的区间的上界的各个数位的值，也就是说取值在[0,9]之间
ll dp[20][5]; //dp数组，记忆化搜索

ll dfs(ll pos/*当前处理到第pos位*/, ll st/*当前有多少个非零位*/, bool limit/*代表数组上界变量*/) //用dfs进行记忆化搜索
{
    if(pos==-1) return 1; //如果dp完每一位，则这个数成立。我的程序最小位编号为0
    if(!limit && dp[pos][st]!=-1) return dp[pos][st]; //记忆化搜索，如果无需考虑限制，之前又算过，则直接返回答案
    ll up=limit?a[pos]:9; //代表这位的最大值是多少
    ll ans=0; //这一位的答案
    for(ll i=0;i<=up;i++)
    {
        if(i==0) ans+=dfs(pos-1,st,limit&&a[pos]==i); //如果这位是零，则st无需加1
        else if(st!=3) ans+=dfs(pos-1,st+1,limit&&a[pos]==i);
    }
    if(!limit) dp[pos][st]=ans; //记忆化搜索
    return ans;
}

ll solve(ll x) //计算[1,x]的答案
{
    ll tot=0;
    //处理出每一位
    while(x>0)
    {
        a[tot++]=x%10;
        x/=10;
    }
    return dfs(tot-1,0,true);
}

int main()
{
    memset(dp,-1,sizeof(dp));
    ll T; 
    cin>>T;
    while(T--)
    {
        ll l,r;
        cin>>l>>r;
        cout<<solve(r)-solve(l-1)<<endl;
        //程序其实有一个问题，就是把零算到了答案里面。但是solve(r)与solve(l-1)都比正确结果大了1，算出来的最终答案还是正确的。
    }
    return 0;
}