[CF846C]Four Segments题解

佚名 6年前 (2019-05-14) 随笔 1016人围观抢沙发百度已收录

我们暴力枚举一下\(delim_{1}\)
然后对于每个\(delim_{1}\)，O(n)扫一遍+前缀和求出最大\(delim_{0}\)和\(delim_{2}\)，然后记录一下它们的位置就行啦

放个代码

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include <cstdio>
#define ll long long

inline ll read(){
    ll x = 0; int zf = 1; char ch = ' ';
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') zf = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;
}

long long qzh[5005];

int main(){
    int n = read();
    for (int i = 1; i <= n; ++i)
        qzh[i] = read();
    for (int i = 1; i <= n; ++i)
        qzh[i] += qzh[i - 1];
    long long cur1, cur2, ans = 0;
    int pos1, pos3, p1 = 0, p2 = 0, p3 = 0;
    for (int i = 0; i <= n; ++i){
        cur1 = cur2 = 0;
        pos1 = 0, pos3 = i;
        for (int j = 0; j <= i; ++j)
            if (qzh[j] - (qzh[i] - qzh[j]) > cur1){
                cur1 = qzh[j] - (qzh[i] - qzh[j]);
                pos1 = j;
            }
        for (int j = i; j <= n; ++j)
            if ((qzh[j] - qzh[i]) - (qzh[n] - qzh[j]) > cur2){
                cur2 = (qzh[j] - qzh[i]) - (qzh[n] - qzh[j]);
                pos3 = j;
            }
        if (cur1 + cur2 > ans){
            ans = cur1 + cur2;
            p1 = pos1;
            p2 = i;
            p3 = pos3;
        }
    }
    printf("%d %d %d", p1, p2, p3);
    return 0;
}