洛谷 P1121 环状最大两段子段和 题解【DP】【环形】

作者: wjyyy 分类: DP,解题报告 发布时间: 2018-06-06 09:03

点击量:32

   典型的动态规划类题目,不过这次在环上,而且是两端,所以DP方法要有所改进。

题目描述

给出一段环状序列,即认为\(A_1\)和\(A_n\)是相邻的,选出其中连续不重叠且非空的两段使得这两段和最大。

 

输入输出格式

输入格式:

第一行是一个正整数\(n(n\le 2\times 10^5)\),表示了序列的长度。

 

第二行包含n个绝对值不大于的整数\(A_i\) ,描述了这段序列,第一个数和第n个数是相邻的。

 

输出格式:

一个整数,为最大的两段子段和是多少。

 

输入输出样例

输入样例#1:
7
2 -4 3 -1 2 -4 3
输出样例#1:
9
   这个题首先看上去是想切环为链,但是发现不是很好控制长度,于是改为做两次,第一次是找不越界的,求最大值。第二次是找不越界的求最小值,也就是这样:
(红色表示被选的块,它们最大)
(红色表示被选的块,而此时蓝色最小)
   这样就避免了切环为链,也方便理解,而且它就是两段。
   重点在于 不能只选一个点,也不能一个点都不选,所以状态转移方程的状态中细节是很多的。
   针对上面的状况,我们把第一段的状态定为1,第二段的状态定为3,第一段与第二段中间的状态为2,最开始没有被选的是0,而最后一段不能为0,不然会出现这种情况:
5  -4  6  -7  4  -3 9
   当状态3结束后,后面的状态是0,但是1也可以从0转移过来,这样序列中就会有无限的1,3,1,3……了。答案总是所有正数之和。
    最终的答案要从所有点的状态3找最值。(第一遍找的是最大值,第二遍找的是最小值。)
  1. 首先,我们的dp数组初始化应为\(-\infty\)。
  2. 我们在转移的过程中,两段是可以连续的,所以3可以从1转移过来。除此之外,2只能从1转移,1从0和1转移,3从1,2,3转移
  3. 在第二遍做时,因为不能一个都不选,所以状态枚举是从1到n-1的。

 

不愧是紫题难度,解题思路也是非常难想的,细节颇多。

 

Code:

#include<cstdio>
#include<cstring>
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
int a[202500];
int f[202500][4];
int main()
{
    int n,sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    memset(f,-0x3f,sizeof(f));
    f[0][0]=0;

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

    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=n;i++)//取两段最小的
    {
        f[i][0]=f[i-1][0];
        f[i][1]=min(f[i-1][0],f[i-1][1])+a[i];
        f[i][2]=min(f[i-1][1],f[i-1][2]);
        f[i][3]=min(min(f[i-1][1],f[i-1][2]),f[i-1][3])+a[i];
    }
    int minn=9999999;
    for(int i=1;i<n;i++)//如果全为负,那么f[n][3]一定是sum,不合题意
        if(f[i][3]<minn)
            minn=f[i][3];


    ans=max(ans,sum-minn);
    printf("%d\n",ans);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */