题目描述：
给定一个区间中，将区间的每一个数看成一个字符串，求这个区间内每个字符串的最大上升
子序列等于k的个数。
可以采用nlogn的LIS(用一个C数组记录长度为i的最大上升子序列的结尾最小值)，
所以可以采用dfs暴力枚举每一个数，并且由于数的长度最大为18位，
所以c数组可以用一个状态数表示。
dp[len][state][k],代表长度为len的数，c数组状态为state，上升子序列长度等于k的个数。
为什么要加k这一维？因为如果有多组询问，k不相同，那么就不能用之前计算过的dp[len][state]状态，
它保存的其实是，上升子序列长度等于之前k的个数。
可以记忆化的理由：分析到如果不同数的前缀对C数组产生的一样，那么两者等价，那么可以记忆化。
个人理解：其实数位DP考虑记忆化，就要从不同前缀对之后len位的影响考虑。
#include <stdio.h> #include <string.h> #include <algorithm> #include <iostream> using namespace std; #define LL long long LL dp[30][1<<10][15]; //长度为30，最大上升子序列状态为s,是否有等于k的个数 int digit[100]; int K; int bit(int state) { int cnt=0; while(state>0) { if(state & 1 ==1) cnt++; state>>=1; } return cnt; } int solve(int state,int i) { int j; int ok=0; for(j=i;j<=9;j++) { if(state & (1<<j)) { ok=1; break; } } int s; if(ok==1) s=( state ^ (1<<j) )| (1<<i); else s=state | (1<< i); return s; } LL dfs(int len,int state,bool z,bool fp) { if( len==0 ) return bit(state)==K; if(!fp && dp[len][state][K] != -1) return dp[len][state][K]; LL ret = 0 ; int fpmax = fp ? digit[len] : 9; for(int i=0;i<=fpmax;i++) { int s=solve(state,i); ret += dfs(len-1,(z&&(i==0)) ? 0 : s, z&&(i==0) ,fp && i == fpmax); } if(!fp) dp[len][state][K] = ret; return ret; } LL f(LL n) { int len = 0; while(n) { digit[++len] = n % 10; n /= 10; } return dfs(len,0,1,true); } int main() { //freopen("test.txt","r",stdin); LL a,b; int t,Case=0; scanf("%d",&t); memset(dp,-1,sizeof(dp)); while(t--) { scanf("%lld%lld%d",&a,&b,&K); if(a==b) printf("Case #%d: %d ",++Case,0); printf("Case #%d: %lld ",++Case,f(b)-f(a-1)); } return 0; }