Four Segments

Four Segments

时间： 1ms        内存：128M

描述：

您将获得一个包含n个整数的数组。设sum（l，r）是区间[l,r)位置上所有数字的总和（计算第l个元素，不计算第r个元素）。0≤l≤r≤n。数组中的索引从0开始编号。

 

例如，如果a = [-5,3,9,4]，则sum（0,1）= -5，sum（0,2）= -2，sum（1,4）= 16

 

选择三个界限符delim0，delim1，delim2（0≤delim0≤delim1≤delim2≤n）和以这样的方式划分阵列的值res = sum(0, delim0) - sum(delim0, delim1) + sum(delim1, delim2) - sum(delim2, n)。让res的值最大。

输入：

第一行包含一个整数n（1≤n≤5000）.

第二行包含n号码一个a0, a1, ..., an-1 (-10^9≤ai≤10^9).

输出：

选择的三个界限符，使res的值最大。如果有多个答案，请打印字典序最小的。

示例输入：

3
-1 2 3

示例输出：

0 1 3

提示：

参考答案（内存最优[1120]）：

#include<stdio.h>
long long int  ans=-1e9;
using namespace std;
int main()
{
    int i,j,k;
    long long int a[5010];
    a[0]=0;
    int n,m,t;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&t);
        a[i]=a[i-1]+t;
    }
    int t1,t2;
    int d1,d2,d3;
    for(j=0;j<=n;j++)
    {
        t1=0;
        for(i=0;i<=j;i++)
        {
            if(a[i]>a[t1])
            {
                t1=i;
            }
        }
        t2=j;
        for(k=j;k<=n;k++)
        {
            if(a[k]>a[t2])
            {
                t2=k;
            }
        }
        if(a[t1]+a[t2]-a[j]>ans)
        {
            ans=a[t1]+a[t2]-a[j];
            d1=t1;
            d2=j;
            d3=t2;
        }
    }
    printf("%d %d %d",d1,d2,d3);
    return 0;
}

参考答案（时间最优[7]）：

#include<bits/stdc++.h>
#define fin             freopen("in.txt","r",stdin)
typedef long long ll;
using namespace std;
const int maxn = 5005;
int a[maxn],l[maxn],r[maxn],x,y,z;
ll sum[maxn],ans=-0x3f3f3f3f;
int main() {
    int n;
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i], sum[i]=sum[i-1]+a[i];
    for (int i=1;i<=n;i++) {
        if (sum[i]>sum[ l[i-1] ]) l[i]=i;
        else l[i]=l[i-1];
    }
    r[n]=n;
    for (int i=n-1;i>=0;i--) {
        if (sum[i]>=sum[ r[i+1] ]) r[i]=i;
        else r[i]=r[i+1];
    }
    for (int i=0;i<=n;i++)
        if(sum[l[i]]-sum[i]+sum[r[i]]>ans) {
            ans=sum[l[i]]-sum[i]+sum[r[i]];
            x=l[i],y=i,z=r[i]; 
        }
    cout<<x<<" "<<y<<" "<<z<<endl;
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。