若要查看题目请访问
设计程序
看完题目，很容易想出题目实际上是想让我们求出数列的最长不上升子序列以及最长上升子序列的长度。n^2的算法无疑很好设计，只要学过线性DP的人应该都很了解，这里就直接给出代码
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
#include <iostream>
#include <cstring>
#include <cstdio>
#define inf 100005
using namespace std;
int n;
int a[inf];
int f[inf];
int ans;
int main() {
int t;
while(cin >> t) {
a[++n] = t;
}
for(int i=1; i<=n; i++) {
f[i] = 1;
for(int j=1; j<i; j++) {
if(a[i] <= a[j]) {
f[i] = max(f[i], f[j]+1);
}
}
// cout << f[i] << " ";
ans = max(ans, f[i]);
}
cout << ans << endl;
memset(f, 0, sizeof(f)); ans = 0;
for(int i=1; i<=n; i++) {
f[i] = 1;
for(int j=1; j<i; j++) {
if(a[i] > a[j]) {
f[i] = max(f[i], f[j]+1);
}
}
ans = max(ans, f[i]);
}
cout << ans << endl;
return 0;
}
这个方法可以过一半的数据，但是仍然不够优秀。我在写本题的时候，很快就想到了优先队列优化的做法
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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define inf 100005
using namespace std;
int n;
int a[inf];
int f[inf];
int ans;
struct heapnode {
int idx, cnt;
bool operator < (const heapnode &T) const {
return cnt < T.cnt;
}
};
priority_queue<heapnode> q;
heapnode tmp[inf];
int p;
int main() {
int t;
while(cin >> t) {
a[++n] = t;
}
for(int i=1; i<=n; i++) {
int k = 0; p = 0;
while(true) {
if(q.empty()) {
break;
}
heapnode t = q.top();
if(a[i] <= a[t.idx]) {
k = t.cnt;
break;
}
tmp[++p] = t; q.pop();
}
for(int j=1; j<=p; j++) {
q.push(tmp[j]);
}
f[i] = max(1, k);
q.push((heapnode){i, f[i]+1});
ans = max(ans, f[i]);
}
cout << ans << endl;
memset(f, 0, sizeof(f)); ans = 0;
while(!q.empty()) {
q.pop();
}
for(int i=1; i<=n; i++) {
int k = 0; p = 0;
while(true) {
if(q.empty()) {
break;
}
heapnode t = q.top();
if(a[i] > a[t.idx]) {
k = t.cnt;
break;
}
tmp[++p] = t; q.pop();
}
for(int j=1; j<=p; j++) {
q.push(tmp[j]);
}
f[i] = max(1, k);
q.push((heapnode){i, f[i]+1});
ans = max(ans, f[i]);
}
cout << ans << endl;
return 0;
}
得分反而更低了。这是因为虽然使用了优先队列，但是代码的最坏时间复杂度还是O（n^2logn）的，再加上STL的开销较大，所以仍然会TLE
到底怎么解决呢？还有更优秀的做法
nlogn优化
我们可以将DP状态设为d[i]，代表的含义为：在最长不上升子序列长度为i时，末尾数字的最大值，并且定义一个len，记录最长不上升子序列
为什么要是最大值呢？
因为最大值在后边求不上升子序列时比最小值更有优势，所以选择最大值
由此，便可以得知：如果循环中a[i]的值不比d[len]大，d[++len] = a[i]
但是现在就又有一个问题，如若a[i] > d[len]，那该怎么办？
这里根据状态的定义，可以在d数组中找到第一个小于a[i]的数，由于a[i]更有优势，便可以将其更改为a[i]。
最长上升子序列也跟此大差不差，自己思考一下即可
代码实现
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
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 100;
int n;
int a[N];
int d1[N], d2[N];
int main() {
while(cin >> a[++n]) {}
n --;
int len1 = 1, len2 = 1;
d1[1] = d2[1] = a[1];
for(int i=2; i<=n; i++) {
if(a[i] <= d1[len1]) d1[++len1] = a[i];
else {
int j = upper_bound(d1+1, d1+1+len1, a[i], greater<int>()) - d1;
d1[j] = a[i];
}
if(a[i] > d2[len2]) d2[++len2] = a[i];
else {
int j = lower_bound(d2+1, d2+1+len2, a[i]) - d2;
d2[j] = a[i];
}
// cout << i << " " << len1 << " " << len2 << endl;
}
cout << len1 << " " << len2 << endl;
return 0;
}
AC愉快
「打开本帖的人RP++」
