hdu_4352_XHXJ's LIS(数位DP+状态压缩)

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4352

题意：这题花大篇篇幅来介绍电子科大的一个传奇学姐，最后几句话才是题意，这题意思就是给你一个LL范围内的区间，问你在这个区间内最长递增子序列长度恰为K的数有多少个

题解：数位DP+状态压缩，这题首先考虑如何来求数位的LIS，很明显不可能用n*n的方法，考虑nlogn的方法，维护的是一个数组，在这里要严格递增，所以最长的LIS小于10，所以我们可以将这个数组用2进制压缩成一个状态，然后这个2进制1的个数就是LIS的值，如果不懂LIS nlogn的原理：传送门，然后再考虑决策状态：由于这题t比较大，只能初始化一次，所以会影响到前面状态的都不能当作决策条件，比如说inf(表示是否达到上限)，当前位置pos，压缩状态s肯定是要的，然后考虑到我们可以对每一个k进行DP，所以要多开一维来保存k，然后dp[i][j][k] 就是dp的状态保存，i表示考虑到当前第i位，j表示当前的压缩状态，k表示LIS恰好为k的答案

#include<cstdio>
#include<cstring>
#define F(i,a,b) for(int i=a;i<=b;i++)
typedef long long LL;

LL n,m,dp[30][1<<10][11];
int t,k,dig[30],len,ic=1;

int getnew(int x,int s){
	F(i,x,9)if(s&(1<<i))return (s^(1<<i))|(1<<x);//维护LIS的数组
	return s|(1<<x);
}
int getnum(int s){
	int ret=0;
	for(;s;s>>=1)if(s&1)ret++;
	return ret;
}
LL dfs(int pos,int s=0,int z=1,bool inf=1){
	if(!pos)return getnum(s)==k;
	if(!inf&&~dp[pos][s][k])return dp[pos][s][k];
	int end=inf?dig[pos]:9;LL ans=0;
	F(i,0,end)ans+=dfs(pos-1,(z&&i==0)?0:getnew(i,s),z&&(i==0),inf&&i==end);
	if(!inf)dp[pos][s][k]=ans;
	return ans;
}

LL f_ck(LL x){
	for(len=0;x;x/=10)dig[++len]=x%10;
	return dfs(len);
}

int main(){
	scanf("%d",&t);
	memset(dp,-1,sizeof(dp));
	while(t--){
		scanf("%I64d%I64d%d",&n,&m,&k);
		printf("Case #%d: %lld\n",ic++,f_ck(m)-f_ck(n-1));
	}
	return 0;
}