n2 过不了惨啊
70分做法
f[i][0] 表示第 i 个作为高的，的最优解
f[i][0] 表示第 i 个作为低的，的最优解
（且第 i 个一定选）
那么
f[i+1][1]=max(f[j][0])+1,i>=j>=1,h[j]>h[i+1],
f[i+1][0]=max(f[j][1])+1,i>=j>=1,h[j]<h[i+1],
——代码
1 #include <cstdio> 2 #include <algorithm> 3 4 const int MAXN = 100001, INF = ~(1 << 31); 5 int n, ans, max; 6 int a[MAXN], f[MAXN][2]; 7 8 inline int Max(int x, int y) 9 { 10 return x > y ? x : y; 11 } 12 13 int main() 14 { 15 //freopen("flower.in", "r", stdin); 16 //freopen("flower.out", "w", stdout); 17 int i, j; 18 scanf("%d", &n); 19 for(i = 1; i <= n; i++) scanf("%d", &a[i]); 20 for(i = 1; i <= n; i++) 21 { 22 max = 0; 23 for(j = 1; j < i; j++) 24 if(a[j] < a[i] && f[j][1] > max) 25 max = f[j][1]; 26 f[i][0] = max + 1; 27 ans = Max(ans, f[i][0]); 28 max = 0; 29 for(j = 1; j < i; j++) 30 if(a[j] > a[i] && f[j][0] > max) 31 max = f[j][0]; 32 f[i][1] = max + 1; 33 ans = Max(ans, f[i][1]); 34 } 35 printf("%d ", ans); 36 return 0; 37 }
100分
我们发现上面的方程可以用线段树优化，可以建一颗权值线段树
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #define root 1, 1, size 5 #define ls now << 1, l, mid 6 #define rs now << 1 | 1, mid + 1, r 7 8 const int MAXN = 100001; 9 int n, size; 10 int a[MAXN], b[MAXN], f[MAXN][2], max[MAXN << 2][2]; 11 12 inline int read() 13 { 14 int x = 0, f = 1; 15 char ch = getchar(); 16 for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1; 17 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0'; 18 return x * f; 19 } 20 21 inline int Max(int x, int y) 22 { 23 return x > y ? x : y; 24 } 25 26 inline void pushup(int now) 27 { 28 max[now][0] = Max(max[now][0], max[now << 1][0]); 29 max[now][0] = Max(max[now][0], max[now << 1 | 1][0]); 30 max[now][1] = Max(max[now][1], max[now << 1][1]); 31 max[now][1] = Max(max[now][1], max[now << 1 | 1][1]); 32 } 33 34 inline int query(int x, int y, int k, int now, int l, int r) 35 { 36 if(x <= l && r <= y) return max[now][k]; 37 int mid = (l + r) >> 1; 38 if(l > y || r < x) return 0; 39 return Max(query(x, y, k, ls), query(x, y, k, rs)); 40 } 41 42 inline void update(int x, int a, int b, int now, int l, int r) 43 { 44 if(l == r) 45 { 46 max[now][0] = Max(max[now][0], a); 47 max[now][1] = Max(max[now][1], b); 48 return; 49 } 50 int mid = (l + r) >> 1; 51 if(x <= mid) update(x, a, b, ls); 52 else update(x, a, b, rs); 53 pushup(now); 54 } 55 56 int main() 57 { 58 int i; 59 n = read(); 60 for(i = 1; i <= n; i++) a[i] = b[i] = read(); 61 std::sort(b + 1, b + n + 1); 62 size = std::unique(b + 1, b + n + 1) - (b + 1); 63 for(i = 1; i <= n; i++) a[i] = std::lower_bound(b + 1, b + size + 1, a[i]) - b; 64 for(i = 1; i <= n; i++) 65 { 66 f[i][0] = query(1, a[i] - 1, 1, root) + 1; 67 f[i][1] = query(a[i] + 1, size, 0, root) + 1; 68 update(a[i], f[i][0], f[i][1], root); 69 } 70 printf("%d ", Max(f[n][0], f[n][1])); 71 return 0; 72 }
100分
用个p线段树，树状数组维护前后缀就好。
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #define root 1, 1, size 5 #define ls now << 1, l, mid 6 #define rs now << 1 | 1, mid + 1, r 7 8 const int MAXN = 1000002; 9 int n, ans; 10 int c0[MAXN], c1[MAXN]; 11 12 inline int read() 13 { 14 int x = 0, f = 1; 15 char ch = getchar(); 16 for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1; 17 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0'; 18 return x * f; 19 } 20 21 inline int max(int x, int y) 22 { 23 return x > y ? x : y; 24 } 25 26 inline int query1(int x) 27 { 28 int ret = 0; 29 for(; x <= MAXN; x += x & -x) ret = max(ret, c1[x]); 30 return ret; 31 } 32 33 inline int query0(int x) 34 { 35 int ret = 0; 36 for(; x; x -= x & -x) ret = max(ret, c0[x]); 37 return ret; 38 } 39 40 inline void update0(int x, int d) 41 { 42 for(; x <= MAXN; x += x & -x) c0[x] = max(c0[x], d); 43 } 44 45 inline void update1(int x, int d) 46 { 47 for(; x; x -= x & -x) c1[x] = max(c1[x], d); 48 } 49 50 int main() 51 { 52 int i, x, y, z; 53 n = read(); 54 for(i = 1; i <= n; i++) 55 { 56 z = read() + 1; 57 x = query1(z + 1) + 1; 58 y = query0(z - 1) + 1; 59 update0(z, x); 60 update1(z, y); 61 ans = max(ans, max(x, y)); 62 } 63 printf("%d ", ans); 64 return 0; 65 }
100分
f[i][0] 表示第 i 个作为高的，的最优解
f[i][0] 表示第 i 个作为低的，的最优解
（然而第 i 个不一定选）
那么
h[i]>h[i−1]时，
f[i][0]=max{f[i−1][0],f[i−1][1]+1},f[i][1]=f[i−1][1];
h[i]==h[i−1]时，
f[i][0]=f[i−1][0],f[i][1]=f[i−1][1];
h[i]<h[i−1]时，
f[i][0]=f[i−1][0],f[i][1]=max{f[i−1][1],f[i−1][0]+1}.
答案ans=max{f[n][0],f[n][1]};
边界为f[1][0]=f[1][1]=1
——代码
1 #include <cstdio> 2 #include <algorithm> 3 4 const int MAXN = 100001, INF = ~(1 << 31); 5 int n, ans; 6 int a[MAXN], f[MAXN][2]; 7 8 inline int max(int x, int y) 9 { 10 return x > y ? x : y; 11 } 12 13 int main() 14 { 15 //freopen("flower.in", "r", stdin); 16 //freopen("flower.out", "w", stdout); 17 int i, j; 18 scanf("%d", &n); 19 for(i = 1; i <= n; i++) scanf("%d", &a[i]); 20 f[1][0] = f[1][1] = 1; 21 for(i = 2; i <= n; i++) 22 { 23 if(a[i] > a[i - 1]) 24 { 25 f[i][0] = max(f[i - 1][0], f[i - 1][1] + 1); 26 f[i][1] = f[i - 1][1]; 27 } 28 else if(a[i] == a[i - 1]) 29 { 30 f[i][0] = f[i - 1][0]; 31 f[i][1] = f[i - 1][1]; 32 } 33 else 34 { 35 f[i][0] = f[i - 1][0]; 36 f[i][1] = max(f[i - 1][1], f[i - 1][0] + 1); 37 } 38 } 39 printf("%d ", max(f[n][0], f[n][1])); 40 return 0; 41 }