P3506 [POI2010]MOT-Monotonicity 2

    • 10通过
    • 76提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 线段树 POI 2010 Special Judge 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    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.

    输入输出样例

    输入样例#1: 复制
    7 3
    2 4 3 1 3 5 3
    < > =
    输出样例#1: 复制
    6
    2 4 3 3 5 3
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。