2

我最近从 INOI 2015 解决了这个问题。在这个问题中，给定两个数组 A 和 B，给定数组的两个索引i和j的特殊总和是A[i]+A[j]加上B 数组中索引在i和j之间的元素。如果您想获得详细的解释，请参阅此处：链接到试卷。试卷给出了一些例子和正式的公式，使问题更清楚。

因此，我继续使用O(n^2)时间算法。

#include <iostream>
#include <cmath>
using namespace std;

#define rep(i,a,b) for(auto (i)=a;i<b;i++)
#define list(i,N) for(auto (i)=0;i<N;i++)

int main(){

    int N; cin >> N;
    int A[N]; list(i,N) cin >> A[i];
    int B[N]; list(i,N) cin >> B[i];
    int prefix[N]; prefix[0] = B[0]; rep(i,1,N) prefix[i] = prefix[i-1]+B[i];

    int maxSum = A[0];
    list(i,N){
        list(j,N){
            if(i == j) maxSum = max(maxSum,A[i]);
            else if(i < j) maxSum = max(maxSum, A[i] + A[j] + prefix[j-1] - prefix[i]);
            else if(i > j) maxSum = max(A[i] + A[j] + prefix[N-1] + prefix[j-1] - prefix[i], maxSum);
        }
    }

    cout << maxSum;

    return 0;
}

基本上我正在计算数组B的前缀总和，并遍历所有索引对i, j。

现在，由于这段代码在O(n^2)时间内运行，我在最后一个测试用例上得到了 TLE，但我希望至少能解决子任务 1 的问题。然而，令我失望的是，这段代码甚至失败了第一个子任务的最后一个测试用例和其他一些分散在其他子任务中的测试用例是 WA（错误答案）。它在前两个测试用例和另一个测试用例上给出了正确答案。其余的我得到一个 TLE（超过时间限制）。我提到了这个讨论：Commonlounge和每个人的O(n^2)算法是我正在使用的相同算法。我也想优化我的代码，但不幸的是我在理解如何在O(n)中做到这一点时遇到了一些麻烦时间。这就是为什么我需要一些帮助。显然有什么问题？一些有用的提示也会很好:)。

任何帮助将非常感激...

谢谢！

4

0 回答 0