「HDU4352」XHXJ's LIS - 数位动规

题目大意

    给定$L,R,K$，对于$[L,R]$的每一个整数，求出每个数数位形成的LIS长度为$K$的个数。

---

题目分析

回忆LIS的$O(n\log n)$非树状数组求法。
我们维护一个上升序列，每次加入值的时候替换掉比他大的第一个数。

因为数位只有$10$位，故我们可以用状压表示这个上升序列，每次更新状态的值。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

LL x,y,k,a[25],f[25][1024][15];

int Next(int status,int x) {
	for(int i=x; i<=9; i++)
		if(status&(1<<i))return status^(1<<i)^(1<<x);
	return status^(1<<x);
}

int Length(int status) {
	int sum=0;
	for(int i=0; i<10; i++)
		if(status&(1<<i))sum++;
	return sum;
}

LL Dp(int Now,int status,bool up,bool zero) {
	if(Now<0)return Length(status)==k;
	if(!up&&~f[Now][status][k])return f[Now][status][k];
	int Limit=up?a[Now]:9;
	LL sum=0;
	for(int i=0; i<=Limit; i++)sum+=Dp(Now-1,(zero&&i==0)?0:Next(status,i),up&&i==Limit,zero&&i==0);
	if(!up)f[Now][status][k]=sum;
	return sum;
}

LL Cal(LL x) {
	int cnt=0;
	while(x) {
		a[cnt++]=x%10;
		x/=10;
	}
	return Dp(cnt-1,0,1,1);
}

int main() {
	memset(f,-1,sizeof(f));
	int t=Get_Int();
	for(int i=1; i<=t; i++) {
		x=Get_Int();
		y=Get_Int();
		k=Get_Int();
		printf("Case #%d: %lld\n",i,Cal(y)-Cal(x-1));
	}
	return 0;
}