[luoguP1970] 花匠（DP）

传送门

n²过不了惨啊

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

上一篇：[POJ3233] Matrix Power Series（矩阵快速幂）

下一篇：[luoguP2601] [ZJOI2009]对称的正方形（二维Hash + 二分 || Manacher）

---

stl DP 线段树 树状数组 离散化