NOIP2013 Day2 T2(贪心/DP+权值线段树)

条件A可看作:
$$g_1 < g_2 > g_3 < g_4 > g_5 < g_m$$
条件B可看作:
$$g_1 > g_2 < g_3 > g_4 < g_5 > g_m$$
感觉像最长上升子序列的DP,改一下然后权值线段树优化到$nlogn$
但是在网上看到了一个解法,统计”拐角数”即可,也就是找到一个最长的序列使得这个序列大小关系交错

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<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
int n, a, b, s, k;
void clean() {}
void init() {
clean();
scanf("%d", &a);
for (int i=1;i<=n;i++) {
scanf("%d", &b);
if (a<b&&k!=1) s++, k = 1;
if (a>b&&k!=2) s++, k = 2;
a = b;
}
printf("%d\n", s+1);
}
void solve() {
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d", &n)==1) init(), solve();
return 0;
}

------ 本文结束 ------