11089: 【原1089】小M的实验室

题目

题目描述

author: 寿鹤鸣 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1089

Description

小M有一片2N个矩形的矩形试验田，并且小M对每个矩形内的适用度进行了评估。他从实验田中选取2Q的区域盖实验室，为了研究方便，

规定在2*Q的区域中第一行选一段长度为P的区域空出来，作为采集样品的场所，此场所将不算作实验室。这样一来，实验室的形状看起来

就是一个“凹”字型。

例如，下图就是一个选取方案，粗线条的区域就是实验基地，它开辟出了一个2*5的区域，并且在第一行中选出了长度为2的样品采集区，

样品采集区的适用度分别为-4和-5。

注意：Q和P在N的范围内可以自行任意选取，但是必须要设置样品采集区，而且样品采集区的左右两侧必须存在实验室。故以下形状的实验

室是不允许出现的：

定义实验室的适用度即为实验室所占据的各个矩形土地的适用度之和，小M希望建立的实验室的适用度尽可能的大，并把实验室选址的认为

交给了你，现在请你用一个算法为其选址。

Input Format

第一行有一个整数N ( 3 < N < 2000 )，

表示试验田的大小是2*N，

随后的两行每行有N个整数(绝对值不超过10^6)，表示对应矩形土地的适用度评估值，各个整数用一个空格隔开。

Output Format

只有一个输出，为整数M，即所确定的实验室的适用度。

Hint

Sample Input

4
-1 2 -3 4
5 6 7 8

Sample Output

31

FineArtz's solution

/* 小M的实验室 */
#include <iostream>
using namespace std;

const int INF = 2000000000;

int main(){
    int n;
    int a[3][2005] = {0}, sum[3][2005] = {0};
    int maxx = -INF, ans = -INF;
    cin >> n;
    for (int i = 1; i <= 2; ++i){
        for (int j = 1; j <= n; ++j){
            cin >> a[i][j];
            sum[i][j]  = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
    for (int i = 3; i <= n; ++i){
        int t = INF, tsum = 0;
        for (int j = i - 2; j >= 1; --j){
            tsum += a[1][j + 1];
            t = min(t, tsum);
            tsum = min(tsum, 0);
            ans = max(ans, sum[2][i] - sum[2][j - 1] - t);
        }
    }
    cout << ans << endl;
    return 0;
}