hdu4352——数位dp+O(nlogn)求LIS+状压

题目链接：https://vjudge.net/problem/HDU-4352

题目大意：

给你一个区间[l,r]，让你求这个区间内符合条件的数的个数。

条件：这个数的数位上的LIS的长度等于k。

 题解：

一道很好的题目，需要知道怎么O(nlogn)求LIS，这样在才能进行状态转移。

如果不懂怎么O(nlogn)求LIS，可以看下我的的博客：https://blog.csdn.net/qq_43472263/article/details/105084063

然后知道怎么求之后我们可以考虑用一个9位的二进制数state表示(1,2,...9)哪些数字出现了。

举个例子：110110000，其中1,2,4,5出现，其中1表示长度为1的上升序列的最小最末元素（类比d数组），

4表示长度为3（前面有3个1，包括自己）的上升序列的最小最末元素，2和5的定义也一样。

在转移状态时，就需要根据上一个状态和当前数位的值更新状态就行了，

类比O(nlogn)的更新方法：如果前面没有比他大的，就直接插入，否则把前面比他大的第一个元素改成它。

最后LIS的长度就是状态state中的1的个数，其实也就是最后的d数组长度。

代码实现：

#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#define PI atan(1.0) * 4
#define E 2.718281828
#define rp(i, s, t) for (register int i = (s); i <= (t); i++)
#define RP(i, t, s) for (register int i = (t); i >= (s); i--)
#define ll long long
#define ull unsigned long long
#define mst(a, b) memset(a, b, sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define debug printf("ac\n");
using namespace std;
inline int read()
{
    int a = 0, b = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            b = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        a = (a << 3) + (a << 1) + c - '0';
        c = getchar();
    }
    return a * b;
}
int a[20],num,k;
ll dp[20][1<<10][10];
int getnew(int x,int s){//类比O(nlogn)维护d数组的操作
    rp(i,x,9)
        if(s&(1<<i))//如果[x,9]有数出现,那么就出现的数的位置变成0（s^(1<<i)）,然后再把第x位变成1（state(|1<<x)）
            return (s^(1<<i))|(1<<x);
	return s|(1<<x);//如果没有数出现,证明当前数比之前的数都大,直接插入,把第x位变为1(s|(1<<x))
}
int getnum(int x){//求状态中1的个数
    int res=0;
    while(x){
        if(x&1) res++;
        x>>=1;
    } 
    return res;
}
ll dfs(int pos,int state,int k,int lead,int limit){
    if(pos==-1) return getnum(state)==k;
    if(!lead&&!limit&&dp[pos][state][k]!=-1) return dp[pos][state][k];
    int up=limit?a[pos]:9;
    ll ans=0;
    rp(i,0,up){
        ans+=dfs(pos-1,(lead&&i==0)?0:getnew(i,state),k,lead&&i==0,limit&&i==a[pos]);
    }
    if(!limit&&!lead) return dp[pos][state][k]=ans;
    return ans;
}
ll solve(ll x){
    num=0;
    while(x) a[num++]=x%10,x/=10;
    return dfs(num-1,0,k,1,1);
}
int main(){
    mst(dp,-1);
    ll l,r;
    int T=read();
    int kcase=0;
    while(T--){
        scanf("%lld%lld%d",&l,&r,&k);
        printf("Case #%d: %lld\n",++kcase,solve(r)-solve(l-1));
    }
    return 0;
}