P2766 最长不下降子序列问题

    • 799通过
    • 3.1K提交
  • 题目提供者 yyy2015c01 管理员
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 最大流 网络流 网络流24题 O2优化
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    «问题描述:

    给定正整数序列x1,...,xn 。

    (1)计算其最长不下降子序列的长度s。

    (2)计算从给定的序列中最多可取出多少个长度为s的不下降子序列。

    (3)如果允许在取出的序列中多次使用x1和xn,则从给定序列中最多可取出多少个长度为s的不下降子序列。

    «编程任务:

    设计有效算法完成(1)(2)(3)提出的计算任务。

    输入输出格式

    输入格式:

    第1 行有1个正整数n,表示给定序列的长度。接下来的1 行有n个正整数n:x1, ..., xn。

    输出格式:

    第1 行是最长不下降子序列的长度s。第2行是可取出的长度为s 的不下降子序列个数。第3行是允许在取出的序列中多次使用x1和xn时可取出的长度为s 的不下降子序列个数。

    输入输出样例

    输入样例#1: 复制
    4
    3 6 2 5
    输出样例#1: 复制
    2
    2
    3

    说明

    $n\le 500$

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。