首页 > 分享 > 花匠（最长波浪子序列——DP + 权值线段树）

花匠（最长波浪子序列——DP + 权值线段树）

花匠小妙招
2024-09-28 14:08

题目描述

花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。
具体而言，栋栋的花的高度可以看成一列整数 h 1 ℎ_1 h1, h 2 ℎ_2 h2, … … … , h n ℎ_n hn。设当一部分花被移走后，剩下的花的高度依次为 g 1 g_1 g1, g 2 g_2 g2, … … … , g n g_n gn，则栋栋希望下面两个条件中至少有一个满足：
条件 A A A：对于所有的 i i i， g 2 i g_{2i} g2i > g 2 i − 1 g_{2i-1} g2i−1，且 g 2 i > g 2 i + 1 g_{2i}>g_{2i+1} g2i>g2i+1；
条件 B B B：对于所有的 i i i， g 2 i < g 2 i − 1 g_{2i}<g_{2i-1} g2i<g2i−1，且 g 2 i < g 2 i + 1 g_{2i}<g_{2i+1} g2i<g2i+1。
注意上面两个条件在 m = 1 m = 1 m=1时同时满足，当 m > 1 m > 1 m>1时最多有一个能满足。
请问，栋栋最多能将多少株花留在原地。

输入

输入的第一行包含一个整数n，表示开始时花的株数。
第二行包含n个整数，依次为 h 1 ℎ_1 h1, h 2 ℎ_2 h2, … … … , h n ℎ_n hn，表示每株花的高度。

输出

输出一行，包含一个整数

样例输入

5 5 5
5 5 5 3 3 3 2 2 2 1 1 1 2 2 2

样例输出

3 3 3

提示

【输入输出样例说明】

有多种方法可以正好保留 3 株花，例如，留下第 1、4、5 株，高度分别为 5、1、2，满足条件 B。

【数据范围】

对于 20 20 20%的数据， n ≤ 10 n ≤ 10 n≤10；
对于 30 30 30%的数据， n ≤ 25 n ≤ 25 n≤25；
对于 70 70 70%的数据， n ≤ 1000 n ≤ 1000 n≤1000， 0 ≤ h i ≤ 1000 0 ≤ ℎ_i≤ 1000 0≤hi≤1000；
对于 100 100 100%的数据， 1 ≤ n ≤ 100 , 000 1 ≤ n ≤ 100,000 1≤n≤100,000， 0 ≤ h i ≤ 1 , 000 , 000 0 ≤ ℎ_i≤ 1,000,000 0≤hi≤1,000,000，所有的 h i ℎ_i hi 随机生成，所有随机数服从某区间内的均匀分布。

题目有点长，说白了就是求原序列的最长波浪子序列
我们可以借鉴求最长上升子序列（ L I S ）（LIS）（LIS）的方法，先想一个 1 D / 1 D 1D/1D 1D/1D的 D P DP DP
状态： f [ i ] [ 0 / 1 ] f[i][0/1] f[i][0/1]表示以 i i i为结尾的最长波浪子序列的长度，且 a [ i ] a[i] a[i]是峰/谷
f [ i ] [ 0 ] = m a x ( f [ j ] [ 1 ] + 1 ) f[i][0] = max(f[j][1] + 1) f[i][0]=max(f[j][1]+1)
f [ i ] [ 1 ] = m a x ( f [ j ] [ 0 ] + 1 ) f[i][1] = max(f[j][0] + 1) f[i][1]=max(f[j][0]+1)
( 1 ≤ j ＜ i ) (1≤j＜i) (1≤j＜i)
初值： f [ i ] [ 0 / 1 ] = 1 f[i][0/1] = 1 f[i][0/1]=1
终值： m a x ( f [ i ] [ 0 / 1 ] ) max(f[i][0/1]) max(f[i][0/1])

然后我们非常开心的发现它超时了o(￣︶￣)o

好，我们现在来用牛刀（权值线段树）杀只鸡
用 b [ i ] [ 0 / 1 ] b[i][0/1] b[i][0/1]表示以值为 i i i为结尾的且 i i i为峰/谷的最长波浪子序列长度那么只要维护这个 b b b数组即可
f [ i ] [ 0 ] = m a x ( b [ j ] [ 1 ] + 1 ) ( 0 ≤ j ＜ i ) f[i][0]=max(b[j][1]+1)(0≤j＜i) f[i][0]=max(b[j][1]+1)(0≤j＜i)
f [ i ] [ 0 ] = m a x ( b [ j ] [ 0 ] + 1 ) ( i ＜ j ≤ m a x h ) f[i][0]=max(b[j][0]+1)(i＜j≤maxh) f[i][0]=max(b[j][0]+1)(i＜j≤maxh)
权值线段树区间查询，单点修改，轻松。

#include<cstdio> using namespace std; const int maxn = 100005; const int maxh = 1000000; int a[maxn] , f[maxn][2]; inline int max(int x , int y){return x > y ? x : y;} inline int read() {char ch = getchar();while(ch < '0' || ch > '9') ch = getchar();int res = 0;while(ch >= '0' && ch <= '9') res = (res << 3) + (res << 1) + (ch ^ 48) , ch = getchar();return res; } struct ST {private:int tree[maxh << 2][2];public:void change(int p , int l , int r , int x , int k , int id){if(l == r){tree[p][id] = max(tree[p][id] , k);return;}int mid = (l + r) >> 1;if(x <= mid) change(p + p , l , mid , x , k , id);else change(p + p + 1 , mid + 1 , r , x , k , id);tree[p][id] = max(tree[p + p][id] , tree[p + p + 1][id]);}int query(int p , int l , int r , int x , int y , int id){if(x > y) return 0;if(l == x && r == y) return tree[p][id];int mid = (l + r) >> 1;if(y <= mid) return query(p + p , l , mid , x , y , id);else if(x > mid) return query(p + p + 1 , mid + 1 , r , x , y , id);else return max(query(p + p , l , mid , x , mid , id) , query(p + p + 1 , mid + 1 , r , mid + 1 , y , id));} }st; int main() {int n = read();for(int i = 1;i <= n;i++) a[i] = read();f[1][0] = f[1][1] = 1;st.change(1 , 0 , maxh , a[1] , 1 , 0);st.change(1 , 0 , maxh , a[1] , 1 , 1);for(int i = 2;i <= n;i++){f[i][0] = st.query(1 , 0 , maxh , 0 , a[i] - 1 , 1) + 1;f[i][1] = st.query(1 , 0 , maxh , a[i] + 1 , maxh , 0) + 1;st.change(1 , 0 , maxh , a[i] , f[i][0] , 0);st.change(1 , 0 , maxh , a[i] , f[i][1] , 1);}int ans = 0;for(int i = 1;i <= n;i++) ans = max(ans , max(f[i][0] , f[i][1]));printf("%dn",ans);return 0; }

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960