https://loj.ac/problem/10164

题目描述

??不降数满足它的数位上的数字从左到右必定时小于等于的关系，求区间\([a,b]\)内不降数的个数。

思路

??我们可以类似的用区间减法把问题转化为\([1,x]\)内的不降数个数，而数位\(dp\)有一个很套路的记忆化搜索的写法，我们记\(pos\)为当前的位数，\(statu\)为状态，\(flag\)记录当前的状态是否为极限状态，那么我们只要依次往每一位填符合条件的数，填完后记录答案即可。对于极限状态的数我们不能用\(dp\)里的值更新，必须单独计算。

代码

#include<bits/stdc++.h>
using namespace std;

int f[20][20],p[20];
int cal(int x,int s,int flag)
{
    if(x==0)return 1;
    if(!flag&&~f[x][s])return f[x][s];
    int res=0,end=flag?p[x]:9;
    for(int i=s;i<=end;i++)
        res+=cal(x-1,i,flag&&i==end);
    if(!flag)f[x][s]=res;
    return res;
}
int solve(int a)
{
    memset(p,0,sizeof(p));
    memset(f,-1,sizeof(f));
    int cnt=0;
    while(a)
    {
        p[++cnt]=a%10;
        a/=10;
    }
    return cal(cnt,0,1);
}

int main()
{
    int a,b;
    while(~scanf("%d%d",&a,&b))
        printf("%d\n",solve(b)-solve(a-1));
} 

数字游戏

原文：https://www.cnblogs.com/fangbozhen/p/11844295.html