[POI2010] MOT-Monotonicity 2
题目描述
This task is a harder version of task Monotonicity from the third stage of 17th Polish OI. It wasn't used in the contest itself.
For an integer sequence 
we define its monotonicity scheme as the sequence 
of symbols 
, 
or 
.
The symbol 
represents the relation between 
and 
.
For example, the monotonicity scheme of the sequence 
is 
.
We say that an integer sequence 
with monotonicity scheme 
, realizes another monotonicity scheme 
if for every 
it holds that 
.
In other words, the sequence 
can be obtained by repeating the sequence 
and removing appropriate suffix from that repetition.
For example, the sequence 
realizes each and every one of the following schemes:
as well as many others.
An integer sequence 
and a monotonicity scheme 
are given.
Your task is to find the longest subsequence 
(
) of the former that realizes the latter.
给出N个正整数a[1..N]，再给出K个关系符号（>、<或=）s[1..k]。
选出一个长度为L的子序列（不要求连续），要求这个子序列的第i项和第i+1项的的大小关系为s[(i-1)mod K+1]。
求出L的最大值。
感谢@cn：苏卿念 提供spj
输入格式
The first line of the standard input holds two integers 
and 
(
, 
), separated by a single space, denoting the lengths of the sequences 
and monotonicity scheme 
respectively.
The second input line gives the sequence 
, i.e, it holds 
integers 
separated by single spaces (
).
Finally, the third lines gives the monotonicity scheme 
, i.e., it holds 
s…
输出格式
In the first line of the standard output your program should print out a single integer 
, the maximum length of a subsequence of 
that realizes the scheme 
.
In the second line it should print out any such subsequence 
, separating its elements by single spaces.
7 3
2 4 3 1 3 5 3
< > =
6
2 4 3 3 5 3
提示
，，，