|
|
思路：
如果之前出现过长度为 len 的子序列。假设该子序列出现在 [a, b] 之间。
那如果存在 1, 2, ... K 任意一个数字出现在 [a, b] 之间，则必然存在一个长度为 len + 1 的非子序列。
代码：
从后往前推。用的是链表。94ms AC。
速度一般，还是不知道那些 0ms 是怎么搞出来的。
有人说可以从前往后推，可能会快一点吧。
 #include <stdio.h>
#define MAX_N 100032
#define MAX_K 10032
  struct node  {
 int idx;
struct node *next;
 };
struct node nodes[MAX_N], *pos[MAX_K];
int N, K, left;
int main()
{
int i, j, len;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &K);
  for (i = 0; i < N; i++) {
scanf("%d", &j);
nodes[i].idx = i;
nodes[i].next = pos[j];
pos[j] = &nodes[i];
 }
left = N + 1;
for (len = 1; len <= N; len++) {
j = left;
for (i = 1; i <= K; i++) {
while (pos[i] && pos[i]->idx >= left)
pos[i] = pos[i]->next;
if (!pos[i])
break;
if (pos[i]->idx < j)
j = pos[i]->idx;
}
if (i <= K)
break;
left = j;
}
printf("%d\n", len);
return 0;
}
|