#PU698. USACO 2017 January Contest, Platinum — Problem 3. Subsequence Reversal

    ID: 1469 传统题 文件IO:subrev 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:jan17来源:usaco.orgscoring:equal_test_cases动态规划

USACO 2017 January Contest, Platinum — Problem 3. Subsequence Reversal

USACO 2017 January Contest, Platinum — Problem 3. Subsequence Reversal

题目描述

Farmer John is arranging his NN cows in a line to take a photo (1≤N≤501 \leq N \leq 50). The height of the iith cow in sequence is a(i)a(i), and Farmer John thinks it would make for an aesthetically pleasing photo if the cow lineup has a large increasing subsequence of cows by height. To recall, a subsequence is a subset a(i1),a(i2),…,a(ik)a(i_1), a(i_2), \ldots, a(i_k) of elements from the cow sequence, found at some series of indices i1<i2<…<iki_1 < i_2 < \ldots < i_k. We say the subsequence is increasing if a(i1)≤a(i2)≤…≤a(ik)a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k). FJ would like there to be a long increasing subsequence within his ordering of the cows. In order to ensure this, he allows himself initially to choose any subsequence and reverse its elements. For example, if we had the list 1 6 2 3 4 3 5 3 4 We can reverse the chosen elements 1 6 2 3 4 3 5 3 4 ^ ^ ^ ^ to get 1 4 2 3 4 3 3 5 6 ^ ^ ^ ^ Observe how the subsequence being reversed ends up using the same indices as it initially occupied, leaving the other elements unchanged. Please find the maximum possible length of an increasing subsequence, given that you can choose to reverse an arbitrary subsequence once.

输入格式

The first line of input contains NN. The remaining NN lines contain a(1)…a(N)a(1) \ldots a(N), each an integer in the range 1…501 \ldots 50.

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

9
1
2
3
9
5
6
8
7
4
9
Problem credits: Lewin Gan