牛客IOI周赛19-提高组 B-翻转

翻转

前言

毒瘤QwQ,凉心出题人

分析

• 题目：何谓翻转？无非是将后面的一段最大子序列加到前面。也就是说，题目要求最大的两段子序列的和(注意断句)。

• 情况：
  情况1:这两段子序列不会越过首尾。
  
  情况2：因为是环状，所以会产生三段子序列
  

• 做法
  采用dp，设f [ 0/1 ] [ 1/2/3 ] [ N ] ，第一维表示当前点是否被选入子序列，第二维表示到这个点的时候前面有多少段
  情况一

  f[0][1][i]=max(f[0][1][i-1],f[1][1][i-1]);//之前有一段，要么上一个点入选，要么没入选
  f[1][1][i]=max((ll)0,f[1][1][i-1])+a[i];
  f[0][2][i]=max(f[0][2][i-1],f[1][2][i-1]);//与1同理
  f[1][2][i]=max(f[0][1][i-1],max(f[1][1][i-1],f[1][2][i-1]))+a[i];//因为当他前面被分为2段的时候，要么从前一个点开始，要么前一个点入选但不是开始，要么前面是第一段的结束点

  情况二

  f[0][1][i]=max(f[0][1][i-1],f[1][1][i-1]);
  f[1][1][i]=f[1][1][i-1]+a[i];
  f[0][2][i]=max(f[0][2][i-1],f[1][2][i-1]);
  f[1][2][i]=max(f[0][1][i-1],f[1][2][i-1])+a[i];
  f[0][3][i]=max(f[0][3][i-1],f[1][3][i-1]);
  f[1][3][i]=max(f[0][2][i-1],max(f[1][3][i-1],f[1][2][i-1]))+a[i];

  代码

/*
    有两种情况：

    1.求三段的最长子序列和 

    2.求两段的最长子序列和 
*/
#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=2e5+10;

int n,cnt;
ll a[N],f[2][4][N];
//f[i][j][k]:到k时,有无选上,之前有几个段
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]);

    ll ans=-2e15;
    for (int i=1;i<=n;i++) ans=max(ans,a[i]);
    if(ans<0)
    {
        printf("%lld\n",ans);
        return 0;
    }

    ans=-2e15;
    memset(f,-0x3f,sizeof(f));
    f[1][1][1]=a[1];
    for (int i=2;i<=n;i++)
    {
        f[0][1][i]=max(f[0][1][i-1],f[1][1][i-1]);
        f[1][1][i]=max((ll)0,f[1][1][i-1])+a[i];
        f[0][2][i]=max(f[0][2][i-1],f[1][2][i-1]);
        f[1][2][i]=max(f[0][1][i-1],max(f[1][1][i-1],f[1][2][i-1]))+a[i];
    }
    ans=max(f[1][2][n],f[0][2][n]);

    memset(f,-0x3f,sizeof(f));
    f[1][1][1]=a[1];
    for (int i=2;i<=n;i++)
    {
        f[0][1][i]=max(f[0][1][i-1],f[1][1][i-1]);
        f[1][1][i]=f[1][1][i-1]+a[i];
        f[0][2][i]=max(f[0][2][i-1],f[1][2][i-1]);
        f[1][2][i]=max(f[0][1][i-1],f[1][2][i-1])+a[i];
        f[0][3][i]=max(f[0][3][i-1],f[1][3][i-1]);
        f[1][3][i]=max(f[0][2][i-1],max(f[1][3][i-1],f[1][2][i-1]))+a[i];
    }
    ans=max(ans,f[1][3][n]);

    printf("%lld\n",ans);

    return 0;
}