【CF933A】 A Twisty Movement

题目

题意翻译
给定一个序列 A，你可以翻转其中的一个区间内的数，求翻转后的序列的最长不下降子序列的长度。（|A|\le 2000,1\le a_i \le 2∣A∣≤2000,1≤a
i
​ ≤2 ）

感谢@touristWang 提供的翻译

题目描述
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 1 , while one holding it high is represented by a 2 2 . Thus, the line of performers can be represented by a sequence a_{1},a_{2},…,a_{n} a
1
​ ,a
2
​ ,…,a
n
​ .

Little Tommy is among them. He would like to choose an interval [l,r] [l,r] ( 1<=l<=r<=n 1<=l<=r<=n ), then reverse a_{l},a_{l+1},…,a_{r} a
l
​ ,a
l+1
​ ,…,a
r
​ so that the length of the longest non-decreasing subsequence of the new sequence is maximum.

A non-decreasing subsequence is a sequence of indices p_{1},p_{2},…,p_{k} p
1
​ ,p
2
​ ,…,p
k
​ , such that p_{1}<p_{2}<…<p_{k} p
1
​ <p
2
​ <…<p
k
​ and a_{p1}<=a_{p2}<=…<=a_{pk} a
p1
​ <=a
p2
​ <=…<=a
pk
​ . The length of the subsequence is k k .

输入输出格式
输入格式：
The first line contains an integer n n (1<=n<=2000) (1<=n<=2000) , denoting the length of the original sequence.

The second line contains n n space-separated integers, describing the original sequence a_{1},a_{2},…,a_{n} a
1
​ ,a
2
​ ,…,a
n
​ (1<=a_{i}<=2,i=1,2,…,n) (1<=a
i
​ <=2,i=1,2,…,n) .

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

输入输出样例
输入样例#1： 复制
4
1 2 1 2
输出样例#1： 复制
4
输入样例#2： 复制
10
1 1 2 2 2 1 1 2 2 1
输出样例#2： 复制
9
说明
In the first example, after reversing [2,3] [2,3] , the array will become [1,1,2,2] [1,1,2,2] , where the length of the longest non-decreasing subsequence is 4 4 .

In the second example, after reversing [3,7] [3,7] , the array will become [1,1,1,1,2,2,2,2,2,1] [1,1,1,1,2,2,2,2,2,1] , where the length of the longest non-decreasing subsequence is 9 9 .

思路

我们显然（事实上考试只想出了解法一）可以用DP来维护每段的最大值。

定义状态f[i][1]表示前ii个数中前一段的答案，f[i][2]表示前ii个数中前两段的答案，f[i][3]表示前ii个数中前三段的答案，f[i][4]表示前ii个数中前四段的答案。

那么不难得到状态转移方程：

f[i][1]=f[i-1][1]+(ai=1)
f[i][2]=max(f[i-1][1],f[i-1][2]+(ai=2))
f[i][3]=max(f[i-1][2],f[i-1][3]+(ai=1))
f[i][4]=max(f[i-1][3],f[i-1][4]+(ai=2))

代码

#include<bits/stdc++.h>
using namespace std;
int n,x,f[5];

int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
	{
		scanf("%d",&x),
		f[1]+=(x==1),
		f[2]=max(f[1],f[2]+(x==2)),
		f[3]=max(f[2],f[3]+(x==1)),
		f[4]=max(f[3],f[4]+(x==2));
	} 
	printf("%d",f[4]);
	return 0;
}