小朋友的博客

日拱一卒,功不唐捐

题解 P1121 环状最大两段子段和

思路

观察题目,发现不管怎么选,都只有两种情况:

1. ++++++---++++---

2. ++---+++++--++++

即要么是选两段的(对应$1.$),要么是有两段不选的(对应$2.$)

这样想就会把环拆成一条链

那么对于$1.$,我们可以从头尾两端去扫描数组,设$f[i]$为$1-i$和最大的连续的一段:

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

这样保证了扫描一遍后的$f[i]$必定是在以$i$结尾一个连续的一段中

但并不是最优的那一段,因为在$1-i$中最优的一段可能不以$i$结尾

所以再扫描一遍数组:

f[i] = max(f[i - 1], f[i]);

便得到了$1-i$中和最大的连续的一段

因为是两段,所以设$g[i]$为$i-n$中和最大的连续的一段,再扫两遍,比较一下:

res = max(res, f[i] + g[i + 1]);//注意因为不重叠,所以是g[i + 1]

这是第一种情况的做法

第二种求最优的三段的和,那么也就是总和减去不要的两段

那么把上面的$max$改成$min$就可以求出不要的两段的和了

更简单的方法:把$a$数组正负翻转,直接跑,最后是$sum+ask()$(因为符号变了)

注意

  • 若全是非正数,第二次跑会返回$0$(全不选),所以要排除这种情况

  • 若只有一个正数,第二次跑会把除它全不选,是错的,要特判

自己想想为什么,对以后的变形会有好处

代码

#include <bits/stdc++.h>

#define MAXN 200010

using namespace std;

int n, ans, sum, positive_num;

int a[MAXN], f[MAXN], g[MAXN];

int ask() {
    int res = -MAXN;
    for (int i = 1; i <= n; i++) f[i] = max(f[i - 1], 0) + a[i];
    for (int i = n; i >= 1; i--) g[i] = max(g[i + 1], 0) + a[i];
    for (int i = 1; i <= n; i++) f[i] = max(f[i - 1], f[i]);
    for (int i = n; i >= 1; i--) g[i] = max(g[i + 1], g[i]);
    for (int i = 1; i < n; i++) res = max(res, f[i] + g[i + 1]);
    return res;
}

int main() {
    scanf("%d", &n);
    memset(f, ~0x7f, sizeof(f));
    memset(g, ~0x7f, sizeof(g));
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        sum += a[i];
        if (a[i] > 0) positive_num++;
    }
    ans = ask();
    if (positive_num == 1) {
        cout << ans << endl;
        return 0;
    }
    for (int i = 1; i <= n; i++) a[i] *= -1;
    ans = max(ans, sum + ask() ? sum + ask() : -MAXN);
    cout << ans << endl;
    return 0;
} 

日拱一卒,功不唐捐


2019-12-01 14:33:35 in 题解