【题意】

问区间[L, R]里面满足 LIS == k的数字个数。

【解题方法】


LIS运用动态规划可以在nlogn的时间复杂度解决，此略。 因为最多只有0-9十个数字，因此可以预处理。 .sta为LIS
的状态，siz[sta]中保存LIS
的长度（即二进制中1的个数),nex[sta][i]为在sta中插入 数字i之后的
状态。 dp[l][sta][k] l为数字长度,sta为当前
的状态，k为所要求的LIS
长度。 dfs(int l,int sta,bool zero,bool jud) ：zero判断是否为前导零，jud为是否为边 界。 注意：dp[l][sta][k]中，k并不是必须的，然而因为本题样例组数过多且k很小，所以选择增加 一维表状态而不是每次都初始化以节约时间。

【AC 代码】

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
inline LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int digit[20],siz[1<<10],nex[1<<10][10];
LL dp[66][(1<<10)][11];
int k;
LL dfs(int l,int sta,bool zero,bool jud){
    if(l==0) return siz[sta]==k;
    if(!jud&&dp[l][sta][k]!=-1) return dp[l][sta][k];
    int nes=jud?digit[l]:9;
    LL ans=0;
    for(int i=0; i<=nes; i++){
        ans+=dfs(l-1,(zero&&i==0)?0:nex[sta][i],zero&&i==0,jud&&i==nes);
    }
    if(!jud) dp[l][sta][k]=ans;
    return ans;
}
LL f(LL num){
    int pos=0;
    while(num){
        digit[++pos]=num%10;
        num/=10;
    }
    return dfs(pos,0,true,true);
}
int find_nex(int status,int num){
    for(int i=num; i<10; i++){
        if(status&(1<<i)) return (status^(1<<i)|(1<<num));
    }
    return status|(1<<num);
}
int main()
{
    LL n,m;
    int T,cas=1;
    memset(dp,-1,sizeof(dp));
    for(int i=0; i<(1<<10); i++){
        siz[i]=0;
        for(int j=0; j<10; j++){
            if(i&(1<<j)) siz[i]++;
            nex[i][j]=find_nex(i,j);
        }
    }
    scanf("%d",&T);
    while(T--){
        m=read(),n=read(),k=read();
        LL ans=f(n)-f(m-1);
        printf("Case #%d: %I64d\n",cas++,ans);
    }
}