HDOJ4352_XHXJ's LIS

XHXJ's LIS

刚发现我写题解从来都没有把题目名字写出来过，从今天开始起补上

又是一个新的数位DP姿势，学完各位大神的博客来自己总结一发

题目链接：HDOJ4352

题意：给定【L，R】，求各个数的数位上数字的LIS为K的数有多少个，看到L，R的数值大小就知道是数位DP，看到K最大是10，也可以猜到K是dp中状态的一维，但是怎么放进去呢？

先想想模板，dp【pos】【status】肯定还是需要的，pos是数位，那么status怎么定义呢？

此题状态定义显然与LIS有关，K最多为10，想到状态压缩，每一个数字0-9是否出现，在status用0或者1表示，所以一个整数可以表示出0-9是否出现过

LIS有种O（nlogn）的做法：

dp【i】：记录LIS长度为i的时候，最后一个数的大小，越小越好的思路

借鉴到这道题来的时候，需要让出现的数字尽可能的小，所以status中，低位出现的1就要尽量多（这就可以写个函数来实现）

既然是LIS长度为K，那么K肯定需要是dp中的一维状态变量

所以状态量定义为dp【pos】【status】【K】，其中status中1的个数就是LIS的长度

然后呢，在LIS中有个特殊情况必须处理好。如果某个数位中已经出现了0，那么之前的LIS就可以断下来了（因为再也不可能更长）

所以在记忆化的时候，需要一个变量来记录是不是当前有0，或者说前导0

剩下的贴代码可以直接懂了，跟模板没有太多区别了

#include<map>
#include<set>
#include<math.h>
#include<time.h>
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<stdio.h>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cstdlib>
using namespace std;

#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define ll rt<<1
#define rr rt<<1|1
#define LL long long
#define ULL unsigned long long
#define maxn 1050
#define maxnum 1000050
#define eps 1e-6
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)

/*
函数解释：
getnewstatus：
LIS的O(nlogn)

getonenum:
计算s中有多少个1 
*/

int digit[50],K;
__int64 dp[50][1<<12][12];
__int64 L,R;

int getnewstatus(int x,int s){
	for(int i=x;i<10;i++)
		if (s&(1<<i)) return (s^(1<<i))|(1<<x);
	//如果在某个高位有可以替代的值
	//用x这位去替代i这一位
	//数值会是更小的 
	return s|(1<<x);
	//找不到的话，就把第x这位添加进去 
}

int getonenum(int s){
	//实参代入时为status 
	int num=0;
	while(s){
		if (s%2) num++;
		s>>=1; 
	}
	return num;
}

__int64 dfs(int pos,int status,bool flag,bool zero){
	if (pos==0) return getonenum(status)==K;
	if (flag&&dp[pos][status][K]!=-1) return dp[pos][status][K];
	int num=flag?9:digit[pos];
	__int64 ans=0;
	for(int i=0;i<=num;i++)
	//注意到0这个特殊数值 
		ans+=dfs(pos-1,zero&&(i==0)?0:getnewstatus(i,status),flag||i<num,zero&&(i==0));
	if (flag) dp[pos][status][K]=ans;
	return ans;
}

__int64 calc(__int64 n){
	int len=0;
	while(n){
		digit[++len]=n%10;
		n/=10;
	}
	return dfs(len,0,0,1);
}

int main(){
	//input;
	memset(dp,-1,sizeof(dp));
	int T;
	scanf("%d",&T);
	for(int Case=1;Case<=T;Case++){
		memset(digit,0,sizeof(digit));
		scanf("%I64d%I64d%d",&L,&R,&K);
		printf("Case #%d: %I64d\n",Case,calc(R)-calc(L-1));
	}
	return 0;
}