单调序列解题报告

单调序列

( t{GISPZJZ}) 有一个长度为 (n) 的序列 (a_1,a_2,dots,a_n)。序列的所有元素都是 (1) 或者 (2)。
我们称一序列是该序列的不下降子序列 (p_1,p_2,dots,p_k)，满足 (1le p_1<p_2<p_3<dots <p_kle n)，且(a_{p_1}le a_{p_2}le dots le a_{p_n})。
现在 ( t{GISPZJZ}) 可以选择序列中的一段区间([L,R])，然后将整段反转，例如挑选区间([2,4]),可以将序列((a_1,a_2,a_3,a_4,a_5))变换为((a_1,a_4,a_3,a_2,a_5))。在此基础上， ( t{GISPZJZ}) 希望在反转后，序列的最长不下降子序列最长。当然， ( t{GISPZJZ}) 也可以选择不反转任何区间。现在要求出最优情况下，序列的最长不下降子序列的长度。

输入：

第一行一个正整数 (n)。
第二行 (n) 个数，分别为 (a_1,a_2,dots,a_n)，满足 (1le a_ile 2)。

输出：

一行一个正整数 (x)，表示答案。

数据范围：

对于(10\%)的数据， (1le nle 10)。
对于(40\%)的数据， (1le nle 200)。
对于(70\%)的数据， (1le n le 2000)。
对于(100\%)的数据， (1le nle 100000)。

思路还是很巧妙的。

最开始想把一串的缩在一起做，发现讨论起来非常麻烦。

观察了一下发现翻转后不就是把(000111)什么的变成了可以选(000111000111)这样类似的了吗？

于是直接划分一下状态( t{DP})即可，是一个非常好的思路啊。

Code:

#include <cstdio>
const int N=1e5+10;
int a[N],dp[N][4],n,ans;
int max(int x,int y){return x>y?x:y;}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i),--a[i];
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=dp[i-1][0]+(a[i]==0);
        dp[i][1]=max(dp[i-1][0],dp[i-1][1])+(a[i]==1);
        dp[i][2]=max(dp[i-1][1],dp[i-1][2])+(a[i]==0);
        dp[i][3]=max(dp[i-1][2],dp[i-1][3])+(a[i]==1);
        ans=max(max(dp[i][0],dp[i][1]),max(dp[i][2],dp[i][3]));
    }
    printf("%d
",ans);
    return 0;
}

2017.11.2