题目链接：洛谷 P11665。
题目即从原序列取出若干个数形成新序列，且原序列中相邻两个数至少取一个，求新序列最少用几个不下降子序列可以覆盖。
考虑贪心，如果原序列的某个数要放进新序列，就把它安排在当前所有不下降子序列中，结尾的数小于等于它的最大的一个后面，找不到就新加一个序列。可以发现，过程中某一时刻，所有不下降子序列的最后一个数都不同，可以用 $2^{21}$ 种状态表示。
于是有一个简单的 DP，记 $f_{i,S}$ 表示当前考虑到第 $i$ 个数，不下降子序列的状态为 $S$ 是否可行。
如果 $f_{i,S}=1$，且 $a_{i+1} \in S$，则 $f_{i+1,S}=1$；同理，如果 $f_{i,S}=1$ 且 $a_{i+2} \in S$，则 $f_{i+2,S}=1$。也就是说，从一个 $f_{i,S}=1$ 的状态，可以一直推到 $f_{j-1,S}=1$，其中 $j$ 是最小的满足 $a_j \notin S$，$a_{j+1} \notin S$ 的数。这个 $j$ 可以通过预处理后暴力得出（对每个位置，预处理 $nxt_{i,x}$ 为大于 $i$ 的最小的 $j$，使得 $a_j=x$；$nxtt_{i,x}$ 为大于等于 $i$ 的最小的 $j$，使得 $a_{j+1}=x$；查询时暴力往后跳）。发现对于一个状态 $S$，重要的只有最大的 $k$ 使得 $f_{k,S}=1$，记这样的 $k$ 为 $g_S$。此时的 $j$ 即为 $g_S + 1$。
然后就可以得出 $g_S$ 的求解方法。考虑从小到大计算，由于 $a_{g_S + 1}$ 和 $a_{g_S + 2}$ 至少要选一个，下一个放进不下降子序列集合的数一定是这两个之一。分类讨论放哪一个数，得出新的 $S’$，再计算 $g_{S’}$ 即可。若此时发现 $S’$ 可以把剩下的序列全部覆盖掉，则更新答案。
总的时间复杂度为 $\mathcal{O}(nV+V^22^V)$，此处 $V=\max{a_i}=21$。
代码：
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
| #include <iostream>
#include <cstdio>
using namespace std;
int n;
int a[5000010];
int nxt[5000010][23],nxtt[5000010][23],las[23];
int f[(1 << 21) + 10],ans = 40;
int cnt[(1 << 21) + 10];
int main()
{
scanf("%d",&n);
for (int i = 1;i <= n;i ++) scanf("%d",a + i);
for (int i = n;i >= 1;i --)
{
for (int j = 1;j <= 21;j ++) nxtt[i][j] = nxtt[las[a[i]]][j];
nxtt[i][a[i + 1]] = i + 1;
for (int j = 1;j <= 21;j ++) nxt[i][j] = las[j];
las[a[i]] = i;
}
for (int i = 1;i <= 21;i ++) nxt[0][i] = las[i];
for (int i = 0;i < (1 << 21);i ++) cnt[i] = cnt[i >> 1] + (i & 1);
for (int i = 0;i < (1 << 21);i ++)
{
if (!f[i] && i) continue;
int Nxt = f[i] + 1;
int res = 0,tnxt = Nxt;
Nxt = n + 10;
for (int j = a[tnxt] - 1;j >= 0;j --)
if ((i >> j & 1) || !j)
{
int tmp = (i & ((1 << 21) - 1 - (1 << j))) ^ (1 << (a[tnxt] - 1));
res = tmp;
for (int k = 0;k < 21;k ++)
{
if (tmp >> k & 1) continue;
int t = nxt[tnxt][k + 1];
if (!t) continue;
for (int w = 0;w < 21;w ++)
{
if (tmp >> w & 1) continue;
int tt = nxtt[t][w + 1];
if (!tt) continue;
Nxt = min(Nxt,tt - 1);
}
}
break;
}
if (Nxt >= n)
ans = min(ans,cnt[res]);
else f[res] = max(f[res],Nxt - 1);
Nxt = n + 10;
for (int j = a[tnxt + 1] - 1;j >= 0;j --)
if ((i >> j & 1) || !j)
{
int tmp = (i & ((1 << 21) - 1 - (1 << j))) ^ (1 << (a[tnxt + 1] - 1));
res = tmp;
for (int k = 0;k < 21;k ++)
{
if (tmp >> k & 1) continue;
int t = nxt[tnxt + 1][k + 1];
if (!t) continue;
for (int w = 0;w < 21;w ++)
{
if (tmp >> w & 1) continue;
int tt = nxtt[t][w + 1];
if (!tt) continue;
Nxt = min(Nxt,tt - 1);
}
}
break;
}
if (Nxt >= n)
ans = min(ans,cnt[res]);
else f[res] = max(f[res],Nxt - 1);
}
printf("%d\n",ans);
}
|