HDU 4352 XHXJ's LIS

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

-----------------------------------------------------------------------------------------

做这题前先要会$LIS$的单调数组&二分的做法

这题状态压缩是很需要技巧的

如果记录构成长度为$x$的$LIS$结尾处最小为几那么需要记录$10!$种状态这样复杂度会很高

然而我们可以发现其实可以只用$2^{10}$大小的数组

然后标记出所有出现在单调数组中的数即可大小关系也直接由位置关系反应出来

至于$f$数组则分别代表还有多少位没有确定目前已经达到的状态需要的$lis$长度

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <algorithm>
 5 using namespace std;
 6 long long f[20][1 << 10][11];
 7 int checked[11][1 << 10], ma[10][1 << 10];
 8 int num[20];
 9 int t, len;
10 int check(int k, int sta)
11 {
12     if(checked[k][sta] != -1)
13         return checked[k][sta];
14     int tk = k;
15     for(int i = 0; i < 10; ++i)
16         if((1 << i) & sta)
17             --tk;
18     return checked[k][sta] = !tk;
19 }
20 int change(int x, int sta, bool zero)
21 {
22     if(!x && zero)
23         return 0;
24     if(ma[x][sta] != -1)
25         return ma[x][sta];
26     for(int i = x; i < 10; ++i)
27         if((1 << i) & sta)
28             return ma[x][sta] = (sta ^ (1 << i) ^ (1 << x));
29     return ma[x][sta] = (sta | (1 << x));
30 }
31 long long dfs(int x, int sta, int k, int top, bool zero)
32 {
33     if(!top && !zero && f[x][sta][k] != -1)
34         return f[x][sta][k];
35     if(!x)
36         return f[x][sta][k] = check(k, sta);
37     long long re = 0;
38     if(top)
39         for(int i = 0; i <= num[x]; ++i)
40             re += dfs(x - 1, change(i, sta, zero && !i), k,
41              i == num[x], zero && !i);
42     else if(zero)
43         for(int i = 0; i <= 9; ++i)
44             re += dfs(x - 1, change(i, sta, i == 0), k, 0, !i);
45     else
46     {
47         for(int i = 0; i <= 9; ++i)
48             re += dfs(x - 1, change(i, sta, 0), k, 0, 0);
49         f[x][sta][k] = re;
50     }
51     return re;
52 }
53 long long calc(long long x, int k)
54 {
55     len = 0;
56     while(x)
57     {
58         num[++len] = x % 10;
59         x /= 10;
60     }
61     return dfs(len, 0, k, 1, 1);
62 }
63 int main()
64 {
65     memset(f, -1, sizeof f);
66     memset(ma, -1, sizeof ma);
67     memset(checked, -1, sizeof checked);
68     scanf("%d", &t);
69     long long x, y;
70     int k;
71     for(int ca = 1; ca <= t; ++ca)
72     {
73         scanf("%lld%lld%d", &x, &y, &k);
74         printf("Case #%d: %lld\n", ca, calc(y, k) - calc(x - 1, k));
75     }
76     return 0;
77 }

HDU 4352 XHXJ's LIS

推荐阅读