CodeForce1036C Classy Numbers

此题题意，在$[l,r]$中，找出非0数不超过3的数的个数

解法

可以定义一个数组$f[n][m][s]$，其中n为数位个数，m为第i位的数，s为非0的数字个数。在做完init之后，剩下的就是进行dp分解了，根据闫氏dp分析法，从高位向低位递推，对于第i位分为$[0,a_i-1],a_i$两种情况，我们只需算第一种情况，同时，每次算时，需一个last值记录非0数的个数对后续dp的影响，在最后判断等于这个数时是否满足，根据情况进行加减

        a[n]  第n位
        / \
       /   \
   0~a[n]-1  a[n-1]
            / \
           /   \
    0~a[n-1]-1  ...
                / \
               /   \
          0~a[0]-1 a[0]

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int l,r,f[20][10][5];
void init(){
    for(int i=0;i<=9;i++)f[1][i][i!=0]=1;
    for(int i=2;i<20;i++)
        for(int j=0;j<=9;j++)
            for(int k=0;k<=9;k++){
                f[i][j][4]+=f[i-1][k][4];
                for(int u=0;u<=3;u++){
                    f[i][j][u+(j!=0)]+=f[i-1][k][u];
                }
            }
}


int dp(int n){
    if(!n)return 1;
    vector<int>nums;
    while(n)nums.push_back(n%10),n/=10;
    int res=0;
    int last=0;
    for(int i=nums.size()-1;i>=0;i--){
        int x=nums[i];
        for(int j=(i==nums.size());j<x;j++){
            for(int k=0;k<=3;k++){
                if(k+last<=3)res+=f[i+1][j][k];
            }
        }
        last+=(x!=0);
    }
    if(last<=3)res++;
    return res;
}

signed main(){
    init();
    int T;
    cin>>T;
    while(T--){
        cin>>l>>r;
        cout<<dp(r)-dp(l-1)<<endl;
    }
}