|
|
思路：
如果之前出現過長度為 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;
}
|