XHXJ‘s LIS_牛客博客

题意：
题目意思就是给你L到R区间，和一个数字K，然后让你求L到R区间之内满足最长上升子序列长度为K的数字有多少个；
比如 $1213$ 就是上升子序列长为 $3$ 的数字

思路：

$dp$ 的状态应该包含长度 $len$ 、状态 $tot$ 、以及题目的要求 $k$ （刚开始没考虑到以后每组的答案受到前面答案的影响，没有多开一维数组存 $k$ 就错了）
最长上升子序列有个 $O(nlogn)$ 的解法， $d$ 数组存最长上升子序列对应有哪些点，这不是它主要的作用，遍历时我们需要把出现在 $LIS$ 中可能性更大的点放进去，所以 $d$ 数组存的有些点不一定是最长上升子序列对应的点，但是 $d$ 数组的长度就是 $LIS$ 的长度。
考虑到 $LIS$ 中最多只有 $10$ 个数字，所以用将 $d$ 数组状压到二进制， $0$ 表示没存这个数， $1$ 表示存了这个数。用位运算模拟 $d$ 数组的操作，只是这里不能用 $O(logn)$ 的 $lower\_bound$ ，所以这里求 $LIS$ 复杂度其实是 $O(n^2)$ 的。

注意前缀零是没用的，因为自然数没有前缀零

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3+7;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
ll dp[20][1<<10|1][11];
int digit[20],k;
inline int update(int x,int sum) {
    for(int i=x;i<10;++i) if((1<<i)&sum)
        return (sum^(1<<i)|(1<<x));
    return sum|(1<<x);
}
ll dfs(int len,int tot,bool zero,bool limit) {
    if(!len) {
        int cnt=0;
        while(tot) {
            if(tot&1) cnt+=1;
            tot>>=1;
        }
        return cnt==k;
    }
    if(!limit&&dp[len][tot][k]!=-1) return dp[len][tot][k];
    int endi=(limit?digit[len]:9);
    ll ans=0;
    for(int i=0,pos;i<=endi;++i) {
        ans+=dfs(len-1,zero&&(i==0)?0:update(i,tot),zero&&i==0,limit&&i==endi);
    }
    if(!limit) dp[len][tot][k]=ans;
    return ans;
}
ll solve(ll n) {
    int len=0;
    while(n) {
        digit[++len]=n%10;
        n/=10;
    }
    return dfs(len,0,true,true);
}
int main() {
    int t=read(),cas=0;
    memset(dp,-1,sizeof dp);
    ll l,r;
    while(t--) {
        l=read(),r=read(),k=read();
        printf("Case #%d: %lld\n",++cas,solve(r)-solve(l-1));
    }
    return 0;
}