水题笔记_ codevs 2185 LCIS [序列DP]

有的时候万能的DP之神也需要一个辅助数组

懵逼的 题目

传送至 Codevs

扯淡的 题解

解释一下数组的意义:

  • 设f[i]为以b[i]结尾的lcis的最大长度
  • k为每一轮枚举时, 可以接在b[i]前面的最长的长度

接下来是算法:

1. 主体算法就是固定一个 a[i], 然后枚举 b[j], 当 `a[i] == b[j]` 时更新 f[j] (即找一个最大的 f[x], 满足b[x] < b[j]) 
2. k是优化时间复杂度的, 原理如下:
1
2
if (a[i] > b[j])
k = max(k, f[j]);

至于 (a[i] > b[j]) 才更新, 是因为下文的a[i] == b[j], 所以如果a[i]大于这个b[j], 以后与a[i]相等的b[j1] (即可以进行更新的b[j1] (因为只有a[i] == b[j1] 的时候才能更新) )都会大于这个b[j]…
就酱(窝是不是语文有点烂)…

沙茶的 题解

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
#define MAXN (3000 + 5)
using namespace std;
int a[MAXN];
int b[MAXN];
int n;
int ans = 0;
int f[MAXN];
void dp();
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; i++)
{
scanf("%d", &b[i]);
}
dp();
printf("%d", ans);
return 0;
}
void dp()
{
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++)
{
int k = 0;
for (int j = 1; j <= n; j++)
{
if (a[i] > b[j])
{
k = max(k, f[j]);
}
if (a[i] == b[j])
{
f[j] = max(f[j], k + 1);
}
}
}
for (int i = 1; i <= n; i++)
{
ans = max(ans, f[i]);
}
}

By 被beat的 Cansult