bzoj 2089/2090: [Poi2010]Monotonicity 2 — 线段树优化dp

  • 2017-12-22
  • 0
  • 0

 

2090: [Poi2010]Monotonicity 2

Time Limit: 30 Sec  Memory Limit: 259 MB

Description

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

Input

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

Output

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

Sample Input

7 3
2 4 3 1 3 5 3
< > =
 

Sample Output

6

 

HINT

选出的子序列为2 4 3 3 5 3,相邻大小关系分别是< > = < >。

Source

很好玩的方式

首先,我们考虑dp,用f[i]表示到第i位时的最长长度

所以这个时候他连接下一位的符号是固定的

这样我们就可以分三类:

如果是=,就开一个桶记录一下值为这个是的当前最优解

如果是<,我们可以推入一个下一位是小于号的线段树,以权值为下表,维护f值

然后下次更新f的时候,取出合法区间的最大的值就好了

如果是>,同理可以维护一个下一位是小于号的线段树

这样就可以做到时间复杂度O(nlogn)了

 

评论

还没有任何评论,你来说两句吧