样例
40
15 30 40 34 12 23 24 1 31 35 22 37 29 21 3 13 33 5 25 32 8 2 4 36 7 38 10 27 18 6 28 26 17 16 9 20 11 39 19 14
40
21 35 2 15 13 14 33 11 22 19 12 9 31 18 5 20 25 28 10 23 1 27 6 24 16 26 29 34 39 7 40 8 17 36 30 3 37 32 38 4
50
42 20 17 25 8 2 34 27 39 29 11 1 4 16 24 21 10 37 22 12 18 28 9 50 19 5 36 13 33 15 7 47 32 31 26 14 49 6 44 41 40 23 35 45 43 46 30 48 3 38
10
1 10 2 9 3 8 4 7 5 6
10
1 2 3 4 5 6 7 8 9 10
10
10 9 8 7 6 5 4 3 2 1
25
1 21 14 11 12 6 13 5 19 17 9 23 16 18 7 22 8 20 15 10 25 3 24 2 4
25
6 11 8 18 12 23 16 3 4 20 7 21 5 24 22 15 25 13 2 19 14 10 9 1 17
0
6
6
8
2
1
1
5
5
算法
(贪心+DFS) $O(n*2^n)$
本题类似与小猫爬山题
- 维护两个up和down的数列.我一开始还用struct来维护,既不直观也超时了
- 只在up中,比当前小,而且最大的数后面深度优先搜索.如果每个数后面都要搜索,妥妥的超时
- 如果在up队列中,没有比自己小的.也就是说我不能从其中任何一个向后拓展,我才开一个新的车.这里的样例有一定误导性.
3 5 2 4 1
应该 写成3 2 1
和5 4
- up 和down是边更新的同时就已经维护了顺序,所以不需要额外的排序
时间复杂度分析:每个数有2种DFS方式,是$2^n$. 每个数的地方都要便利up和down,再乘以n
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
int N;
int v[60];
int res = 60;
int up[60];
int down[60];
void dfs(int index, int upCount, int downCount) {
if (upCount + downCount >= res) { return; }
if (index == N) {
res = upCount + downCount;
return;
}
int curr = v[index];
int i,back;
//up是上升序列,要选一个最大的值
//所以要从大到小排序
//选择第一个比我小的
//就是我能接受的最大的
for (i = 1; i <= upCount && up[i] > curr; i++) {}
back = up[i];
up[i] = curr;
dfs(index + 1, max(i, upCount), downCount);
up[i] = back;
//down是下降序列
//所以要从小到大排序
//选择第一个比我大的
//就是我能接受的最小的
for (i = 1; i <= downCount && down[i] < curr; i++) {}
back = down[i];
down[i] = curr;
dfs(index + 1, upCount, max(i, downCount));
down[i] = back;
}
int main() {
while (1) {
cin >> N;
if (!N) { return 0; }
res = 60;
for (int i = 0; i < N; i++) {
cin >> v[i];
}
dfs(0, 0, 0);
cout << res << endl;
}
}