934C A Twisty Movement(前缀和+思维)

A Twisty Movement

题意

给出n个数字，由1、2组成，你可以选择一个区间[L,R]，将其逆转，使得集合中的**非递减子序列**最长。

（不是子串。。。）

思路

“ 由于序列只由1和2组成，显然我们需要找到最长非递减子序列中第一个2出现的位置pos，那么逆序后[l,pos]会使后面2个数目增加，[pos,r]会使前面1个数目增加。

于是我们先处理出“1”的前缀个数和与“2”的后缀个数和，然后我们每次枚举前面提到的位置pos，然后再依次枚举区间的l和r。

然后分别滑动L，R的值，计算其对最长不降子序列贡献的最大值。

对于l,计算[1,L-1]中1的个数和[l,pos]中2的个数和的最大值。

对于2,计算[R,n]中2的个数和[pos,r-1]中1的个数和的最大值。” （网络）

看！代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,ans=0;
    scanf("%d",&n);
    vector<int>a(n+2);
    vector<int>pre1(n+2);
    vector<int>pre2(n+2);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        pre1[i]=pre1[i-1]+(a[i]==1);
    }
    for(int i=n;i>=1;i--)
        pre2[i]=pre2[i+1]+(a[i]==2);
    for(int k=1;k<=n+1;k++)
    {
        int t1=0,t2=0;
        for(int i=1;i<=k;i++)
            t1=max(t1,pre1[i-1]+pre2[i]-pre2[k]);
        for(int i=k;i<=n+1;i++)
            t2=max(t2,pre2[i]+pre1[i-1]-pre1[k-1]);
        ans=max(ans,t1+t2);
    }
    printf("%d\n",ans);
    return 0;