Description
给出一个 $1$ ~ $n$ 的排列的最长上升子序列的长度 $k$ 以及这个序列，请你求出原排列可能的种类数，数据保证答案小于 $2^{31}$ 。
Solution
考虑使用 状压 DP 来解题。
考虑原排列在什么情况下合法，发现原排列合法的充要条件是 给出的子序列是原排列的子序列 以及 原排列的最长上升子序列长度为 $k$ 。
发现如果记录下当前所选状态的最长上升子序列的话不行，于是可以联想到 $O(n \log n)$ 求最长上升子序列的方法，记录下每个数是否在求最长上升子序列的队列中即可。
于是我们可以设 $f[S]$ 表示当前选的数的状态为 $S$ 的方案数。
其中 $S$ 为一个三进制数，第 $i$ 位为 0 表示该数未选，第 $i$ 位为 1 表示该数选了并且在队列中，第 $i$ 位为 2 表示该数选了但是不在队列中。
然后就可以转移了。
注意如果是用 DP 来转移的话不能将 1 和 2 的定义调换，因为这样可能会由一个较大的状态转移到一个较小的状态去，造成答案错误。
当然如果要调换 1 和 2 的定义的话也可以用 BFS 来进行转移，交由读者练习。
注意三进制状态与二进制状态在转移上的区别，在本题中不要乱用 & 、 | 、 ^ 等符号。
Code
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
| #include <cstdio>
#define maxN 15
#define maxM 15
int f[14348917], a[maxN + 1], b[maxM + 1], c[maxM + 1];
int pow[maxM + 1], bj[maxM + 1];
int main ()
{
pow[0] = 1;
for(int i = 1;i <= maxM; i++)
{
pow[i] = pow[i - 1] * 3;
}
int ans = 0, m = 0, n = 0;
scanf("%d %d", &m, &n);
for(int i = 1;i <= n; i++)
{
scanf("%d", &a[i]);
bj[a[i]] = i;
}
int ma = pow[m] - 1;
f[0] = 1;
for(int S = 0;S <= ma; S++)
{
if(f[S])
{
int len = 0, now = S;
while(now)
{
b[++len] = now % 3;
now /= 3;
}
int len2 = 0;
for(int i = 1;i <= len; i++)
{
if(b[i] == 1)
{
c[++len2] = i;
}
}
for(int i = 1;i <= m; i++)
{
if(b[i])
{
continue;
}
if(bj[i])
{
bool flag = true;
for(int j = 1;j < bj[i]; j++)
{
if(!b[a[j]])
{
flag = false;
break;
}
}
if(!flag)
{
continue;
}
}
if(i > c[len2])
{
if(len2 + 1 <= n)
{
f[S + pow[i - 1]] += f[S];
}
}
else
{
int l = 1, r = len2;
while(l < r)
{
int mid = (l + r) / 2;
if(c[mid] < i)
{
l = mid + 1;
}
else
{
r = mid;
}
}
if(c[l] > i)
{
f[S + pow[c[l] - 1] + pow[i - 1]] += f[S];
}
}
}
bool flag = true;
for(int i = 1;i <= m; i++)
{
if(!b[i])
{
flag = false;
}
}
if(flag)
{
ans += f[S];
}
}
}
printf("%d", ans);
return 0;
}
|