Codeforces 933 A. A Twisty Movement （dp）

Codeforces 933 A. A Twisty Movement （dp）

Description

A dragon symbolizes wisdom, power and wealth. On Lunar New Year’s Day, people model a dragon with bamboo strips and clothes, raise them with rods, and hold the rods high and low to resemble a flying dragon.A performer holding the rod low is represented by a 1, while one holding it high is represented by a 2. Thus, the line of performers can be represented by a sequence a1, a2, ..., an a 1 ,   a 2 ,   . . . ,   a n Little Tommy is among them. He would like to choose an interval [l, r] (1 ≤ l ≤ r ≤ n) [ l ,   r ]   ( 1   ≤   l   ≤   r   ≤   n ) , then reverse al, al + 1, ..., ar a l ,   a l   +   1 ,   . . . ,   a r A non-decreasing subsequence is a sequence of indices p1, p2, ..., pk p 1 ,   p 2 ,   . . . ,   p k , such that p1 < p2 < ... < pk p 1   <   p 2   <   . . .   <   p k and ap1 ≤ ap2 ≤ ... ≤ apk a p 1   ≤   a p 2   ≤   . . .   ≤   a p k . The length of the subsequence is k k

Input

The first line contains an integer n (1 ≤ n ≤ 2000)n (1 ≤ n ≤ 2000)The second line contains n n space-separated integers, describing the original sequence a1, a2, ..., an (1 ≤ ai ≤ 2, i = 1, 2, ..., n)a1, a2, ..., an (1 ≤ ai ≤ 2, i = 1, 2, ..., n)

Output

Print a single integer, which means the maximum possible length of the longest non-decreasing subsequence of the new sequence.

Examples input

41 2 1 2

Examples output

4

题意

在一个只包含 1,2 1 , 2

思路

正着倒着预处理出每一段的 LIS，分别记为 L[i][j],R[i][j] L [ i ] [ j ] , R [ i ] [ j ]

然后开始枚举，翻转一个区间相当于减去这段区间的贡献，然后加上其翻转以后的

此时 LIS 为 L[0][n−1]−L[i][j]+R[i][j] L [ 0 ] [ n − 1 ] − L [ i ] [ j ] + R [ i ] [ j ]

AC 代码

#include#define IO ios::sync_with_stdio(false);\ cin.tie(0);\ cout.tie(0);using namespace std;typedef __int64 LL;const int maxn = 2e3+10;int n;int a[maxn];int L[maxn][maxn],R[maxn][maxn];int main(){ IO; cin>>n; for(int i=0; i>a[i]; for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。