题目大意
Vjudge链接
定义一个数的内部LIS长度表示这个数每个数位构成的序列的LIS长度，给出区间\([l,r]\)，求区间内内部LIS长度为\(k\)的数的个数。
输入格式
第一行给出数据组数\(T\)。
每组数据给出三个数，分别为\(l、r、k\)。
数据范围
\(0<L\le R<2^{63}，1\le K\le 10\)
输出格式
对于每组数据\(t\)，输出Case #t：ans。
\(ans\)表示本组数据符合条件数的个数。
样例输入
样例输出
思路
- 首先处理区间还是用类似前缀和的方法，把\([l,r]\)处理成\([0,r]-[0,l-1]\)。
- 可以看出数据范围是很大的，直接用原始方法求LIS肯定不行，因此本题采用的方法就是状态压缩DP。
- 状态压缩的二进制数中的第\(i\)个1的位置，表示以\(i\)作为序列的LIS最小是多少。最后统计1的个数，则1的个数即为LIS的长度。
- 其他类似普通的LIS的操作，修改0和1即可。
代码
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;//记得用long long
ll T,l,r,k;
ll dp[25][1<<10][15];//分别为当前数位，状态压缩二进制数，要求的LIS长度
ll bit[25];//储存每位的数字
int update(int x,int y){
for (int i=x;i<10;++i)
if (y&1<<i)return (y^(1<<i)|(1<<x));//x位替换x后第一个1
return y|(1<<x);//这是x最大的情况，直接把x位变成1即可
}
int getans(int x){//求1的个数
int ans=0;
while(x){
if (x&1)
ans++;
x>>=1;
}
return ans;
}
ll dfs (int pos,int s,bool e,bool z){
//pos：位数计数器，s：LIS状态，e：边界判定，z：前面所有位是否全都是0
if(pos==-1)
return getans(s)==k;//判断是否符合要求
if(!e&&dp[pos][s][k]!=-1)
return dp[pos][s][k];//记忆化剪枝
ll ans=0;
int lastnum=e ? bit[pos] : 9;
for(int i=0;i<=lastnum;++i)
ans+=dfs(pos-1,(z&&i==0) ? 0 : update(i,s),e&&i==lastnum,z&&(i==0));//向下传递
if(!e)dp[pos][s][k]=ans;//记忆化剪枝
return ans;
}
ll Solve(ll n){
int len=0;
while(n){//求出每位的数字并储存在bit数组中
bit[len++]=n%10;
n/=10;
}
return dfs(len-1,0,1,1);
}
int main(){
memset(dp,-1,sizeof dp);
scanf("%lld",&T);
int casenum=0;
while (T--){
scanf("%lld%lld%lld",&l,&r,&k);
printf("Case #%d: ",++casenum);
printf("%lld\n",Solve(r)-Solve(l-1));
}
return 0;
}