能不能问下,编程比赛是怎么回事啊?我还以为什么时候都可以交呢

在关于比赛的帖子里有比赛时间要求

标准解法没听懂？能具体解释下么？
不知道thomas能否告知标程在这几个case的耗时啊？:)

p.s. 也可以帮senzeng试试嘛，或者直接给出测试数据让他自己测

这里最大的数据也只有20000.而原题有300000
标准做法用堆,O(NLOGN),还有一种做法用队列,O(N)的复杂度,过300000的数据也只要100MS

楼主能否给出用队列实现的代码？

这是标准的最大子段和，DP是典型解法，O(n)
a[]为序列，b[]保存前若干项的最大字段和。状态转移方程b[j] = max{ b[j-1] + a[j] , a[j] } , 1 <= j <= n。 
任意一本介绍DP的书，这道题都是典型例题。google也很容易找到代码


PS：这次的2道题都很容易找到解题报告，不知道是否因为这个原因导致人气不高。太典型的OI/ACM题还是不要直接拿过来的好，至少应该稍微修改一下。我以前AC过的代码几乎可以直接贴过来，所以实在没兴趣参加。

对子段的长度无限制，当然简单，但是对子段的长度有限制就不一样了
ＰＳ：现在找不到题解的题实在是太少了

题解:
http://www.programfan.com/club/showbbs.asp?id=195598

// 根据堆实现改编的队列实现
__int64 MaxSum(int a[], int n, int l1, int l2)
{
    __int64        max;    
    __int64        temp;
    __int64        *sum;    
    __int64        s;        
    int            *queue;    
    int            i;
    int            f, r;

    max = -INT_MAX;
    max *= INT_MAX;

    sum = new __int64[n+1];
    assert(sum != NULL);
    queue = new int[n+1];
    assert(queue != NULL);

    s = 0;
    f = 1;
    r = 0;

    sum[0] = 0;
    for(i=1; i<=n; ++i)
    {
        s += a[i-1];
        sum[i] = s;

        if(i < l1)
            continue;

        while(f<=r && i-queue[f]>l2)
            ++f;

        while(f<=r && sum[i-l1]<=sum[queue[r]])
            --r;
        ++r;
        queue[r] = i - l1;    
        temp = s - sum[queue[f]];    
        if(temp > max)
            max = temp;
    }

    delete []sum;
    delete []queue;

    return max;
}

能不能发下测试代码啊?