传送门
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 12 13 int main() 14 35 printf("%d\n", ans); 36 return 0; 37 }View Code
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 20 21 inline int Max(int x, int y) 22 25 26 inline void pushup(int now) 27 33 34 inline int query(int x, int y, int k, int now, int l, int r) 35 41 42 inline void update(int x, int a, int b, int now, int l, int r) 43 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 70 printf("%d\n", Max(f[n][0], f[n][1])); 71 return 0; 72 }View Code
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 20 21 inline int max(int x, int y) 22 25 26 inline int query1(int x) 27 32 33 inline int query0(int x) 34 39 40 inline void update0(int x, int d) 41 44 45 inline void update1(int x, int d) 46 49 50 int main() 51 printf("%d\n", ans); 64 return 0; 65 }View Code
100分
f[i][0] 表示第 i 个作为高的，的最优解
f[i][0] 表示第 i 个作为低的，的最优解
（然而第 i 个不一定选）
那么
h[i]>h[i−1]时，
f[i][0]=max,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.
答案ans=max;
边界为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 12 13 int main() 14 28 else if(a[i] == a[i 1]) 29 33 else 34 38 } 39 printf("%d\n", max(f[n][0], f[n][1])); 40 return 0; 41 }View Code
上一篇：[luoguP2601] [ZJOI2009]对称的正方形（二维Hash + 二分 || Manacher）
下一篇：[luoguP1631] 序列合并（堆 || 优先队列）
DP 线段树 stl 离散化 树状数组
