第43次编程比赛第二题题目 — 编程爱好者社区

主题：第43次编程比赛第二题题目

thomas [专家分：180] 发布于 2006-10-02 10:28:00

A simple problem

有N个数字，从中选择出连续M(L1<=M<=L2)个数，求出他们之和的最大值

Input
本题有多组测试数据。输入文件第一行有一个数K，表示测试数据的组数。接下来有K组数据，每组数据第一排有三个数N, L1, L2。接下来的一行有N个数，每个数之间用一个空格隔开。 1<=L1<=L2<=N, 1<=N<=20000, -2*10^9<=每个数<=2*10^9

Output
一个数字，表示求出来的和的最大值

输入文件为:DATA2.IN
输出文件为:ANS2.OUT

Sample Input

2

5 1 3

4 -1 2 7 -5

5 3 3

1 2 7 -9 3

Sample Output

9

10

Source
SuperMKR

HINT:数据结构是关键[em2]

本帖地址： http://bbs.pfan.cn/post/195224.html

回复列表（共4个回复）

沙发

thomas [专家分：180] 发布于 2006-09-30 19:38:00

test

板凳

flypampas [专家分：30] 发布于 2006-10-01 16:18:00

我的程序：
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<vector>
using namespace std;

long Max(int N,int L1,int L2,vector<long>a)
{
    long max=-2147483628,sum=0;
    int M;
    for(M=L1;M<=L2;M++)
    {
        for(int i=0;i<N-M+1;i++)
        {
            for(int j=i;j<M+i;j++)
             sum+=a[j];
            if(sum>max)
                max=sum;
            sum=0;
        }
    }
    return max;
}

int main()
{
    ifstream infile;
    ofstream outfile;
    infile.open("DATA2.IN");
    if(!infile)
    {
        cerr<<"不能打开文件data2.in";
        exit(0);
    }
    outfile.open("ANS2.OUT");
    vector<long>a;
    int k,N,L1,L2;
    long temp,result;
    infile>>k;
    for(int i=1;i<=k;i++)
    {
        infile>>N>>L1>>L2;
        for(int j=0;j<N;j++)
        {
            infile>>temp;
            a.insert(a.end(),temp);
        }
        result=Max(N,L1,L2,a);
        outfile<<result<<endl;
        a.clear();
    }
    return 0;
}

3 楼

bood [专家分：490] 发布于 2006-10-01 19:11:00

#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

const char * input="DATA2.IN";
const char * output="ANS2.OUT";

//ans[i]=max sum end with i
long long ans[300000];

//m[i]=max sum end with i no longer than L2-L1, len[i]=length of the max sum
long long m[300000], len[300000];

//number series
long long data[300000];

//sum of L1 numbers end with i
long long shortest[300000];
int main()
{
    ifstream fin(input);
    ofstream fout(output);
    int k;
    fin>>k;
    while(k--)
    {
        int n,l1,l2;
        fin>>n>>l1>>l2;
        for(int i=0;i<n;i++) fin>>data[i];

        shortest[0]=data[0];
        for(int i=1;i<n;i++) {
            shortest[i]=shortest[i-1]+data[i];
            if(i-l1>=0) shortest[i]-=data[i-l1];
        }

        if(l2>l1)
        {
            m[0]=data[0];len[0]=1;
            for(int i=1;i<n;i++) {
                if(m[i-1]>0 && len[i-1]<l2-l1) {
                    m[i]=m[i-1]+data[i];
                    len[i]=len[i-1]+1;
                }
                else if(len[i-1]>=l2-l1)
                {
                    long long sum=data[i],max=data[i];
                    int length=1;
                    for(int k=i-1;i-k+1<=l2-l1&&k>=0;k--)
                    {
                        sum+=data[k];
                        if(sum>max) {
                            max=sum;
                            length=i-k+1;
                        }
                    }
                    m[i]=max;
                    len[i]=length;
                }
                else {
                    m[i]=data[i];
                    len[i]=1;
                }
            }
        }
        else {
            for(int i=0;i<n;i++) m[i]=-1;
        }

        long long ans=shortest[l1-1];
        for(int i=l1;i<n;i++) {
            if(m[i-l1]>0) ans=max(ans,shortest[i]+m[i-l1]);
            else ans=max(ans,shortest[i]);
        }

        fout<<ans<<endl;
    }
    return 0;
}

4 楼

thomas [专家分：180] 发布于 2006-10-02 20:07:00

time's out[em1][em1]

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：第43次编程比赛第二题题目

回复列表（共4个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：第43次编程比赛第二题题目

回复列表 （共4个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共4个回复）