隐藏
「HDU4352」XHXJ's LIS - 数位动规 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

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

题目大意

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


题目分析

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

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


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#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;
}
姥爷们赏瓶冰阔落吧~