标签 - BZOJ

? BZOJ ?    2017-03-19 20:39:14    212    0    0

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,相邻大小关系分别是< > = < >。

link

好神啊!根本做不来TAT

第一眼 次方级暴力算法
想了一会 好像可以DP
然后发现看错题了。。。。。。(不要问我为什么那么傻
又读了一遍题,发现还是可以DP
想了一个n3的大暴力
又优化了一下成了n2logn
然后又想了一个n2的办法
然后就根本没有想到其他的了。。。
想不出来。。。想不出来。。。只有去看题解了
发现是我dp的状态不对只用保留每个数在最终序列中最靠后的可行位置即可
因为是求最长,可以从后往前证明只用保留最靠后的可行位置不会使答案变小。于是就愉快数据结构优化一下就可以了。

P.S:我原来读错题的版本也是一个DP,只不过原有i