BZOJ2090 [Poi2010]Monotonicity2 线段树+DP

发布于 2017-07-27  3.39k 次阅读


[toggle hide="yes" title="题目" color=""]

题目描述

给出N个正整数a[1..N],再给出K个关系符号(>、<或=)s[1..k]。
选出一个长度为L的子序列(不要求连续),要求这个子序列的第i项和第i+1项的的大小关系为s[(i-1)mod K+1]。
求出L的最大值。

输入

第一行两个正整数,分别表示N和K (N, K <= 500,000)。
第二行给出N个正整数,第i个正整数表示a[i] (a[i] <= 10^6)。
第三行给出K个空格隔开关系符号(>、<或=),第i个表示s[i]。

输出

一个正整数,表示L的最大值。

样例输入

样例输出

[/toggle]

线段树优化DP,这题可以类比最长上升子序列的做法。设f[i]为前i位选上第i位后的最优解,则f[i]=max{f[j]}+1。j是满足要求的转移点。因为计算出f值后,序列中最后一个关系符号已经确定,所以可以分情况搞。开两颗权值线段树,每颗树上的元素表示序列中权值为a[i]的数对应的最大f值,对大于号和小于号分别建树,每次区间查询最大值+单点修改即可。对于等号,开个数组记录权值为i的数所对应的最大f值,直接更新即可。

[toggle hide="no" title="代码" color=""]

 

[/toggle]


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974