Sicily 1091 Maximum Sum(SOJ 1091)「dp动态规划」

0.00 avg. rating (0% score) - 0 votes
转载请注明: 吹水小镇 | reetsee.com
原文链接地址: http://blog.reetsee.com/archives/28

原题地址:点击打开链接

题目之前一直有打算做,但是到近来才马力去想,可惜的是没想到呃

肯定很多人觉得这题很水,有很多人第一眼看到答案,或者做出来之后,就忽然觉得这题很水····

可惜我天资不太行,虽然写完后代码只有寥寥几十行,但还是没觉得它水····


————正题————

以sample input为例,对于这个序列:

1 -1 2 2 3 -3 4 -4 5 -5

有一个还算比较容易想到的是:要将序列分成左边和右边两个部分。

应当注意到两个部分的特征是(假设左边为A,右边为B),A部分的某个连续字串构成了A的最大连续和(记为AM),B的同理。最终结果则是AM+BM。

对于整个字符串来说,如果有N个数字,那么可以划分的情况为N-1种,在N-1种情况中挑最大的即可。

现在问题就在于怎么找到AM和BM,以A={3, 2, -1, 2, 4}为例子,显然仅仅比较连续的整数和(即3+2与2+4)是不行的,因为3+2+(-1)+2+4的结果是最大的,然而如果对于A={3, 2, -100, 2, 4},那么很明显AM=6。如何知道碰到一个负数的时候是应该把它也先加上(如第一种情况),还是把它抛弃掉(如第二种情况)呢?

上面那个问题就是当时我的思考瓶颈,在继续谈上面那个问题之前,我想说一个很关键的思考方法,对于解这道题,我觉得一直想着怎么去找子串可能会有所困难。但是如果能够想到为每一个下标加2个属性:1.从左边到当前位置,最大的连续和是多少    2.从右边到当前位置,最大连续和是多少。好了继续说题

碰到负数时,如果当前的连续和的绝对值小于或等于该负数的绝对值,那么就丢弃掉那个负数,并将当前连续和设置为0,在下一个位置重新计算连续和。否则,如果没有大于,那么可以先加上该负数。再计算过程中,每次移动到新下标检查一次连续和,如果大于之前统计的最大值,那么就更新最大值,并更新属性1 。对于属性1,随着下标的递增,是非递减的;对于属性2,随着下标的递增,是非递增的。

对于A,按照上述的计算方法(从左到右),其属性1的值如下:

+++

              A串:1  -1  2  2  3  -3  4  -4  5  -5

当前连续和:1    0  2  4  7   4  8    4  9   4

最大连续和:1    1  2  4  7   7  8    8  9   9

+++

对于B,注意此时是从右到左计算

+++

              B串:1  -1  2  2  3  -3  4  -4  5  -5

当前连续和: 9   8  9  7  5   2   5   1  5  -5

最大连续和: 9   9  9  7  5   5   5   5  5  -5

+++

则,此时我们可以从这个集合中选取最大的一个max{1+9, 1+9, 2+7, 4+5, 7+5, 7+5, 8+5, 8+5, 9+(-5)  } = 13

代码如下:

#include<stdio.h>
#include<iostream>
#include<cmath>
#include<algorithm>
#define MAX 50005
#define MIN -500000009
using namespace std;
long long a[MAX];
long long ltr[MAX]; //left to right
long long cs,cm;    //current sum, current max
int n;
int main()
{
    int tc;
    cin>>tc;
    while(tc--)
    {
        cin>>n;
        for(int i=0;i<n;++i)
            scanf("%lld",&a[i]);

        cm=MIN;
        cs=0;
        for(int i=0;i<n;++i)
        {
            cs+=a[i];
            if(cs>cm)
            {   
                cm=cs;
                ltr[i]=cm;
            }
            else
                ltr[i]=ltr[i-1];
            if(cs<0)
             cs=0;
        }
        cs=0;
        cm=MIN;
        long long ans=MIN;     //answer
        for(int i=n-1;i>0;--i)
        {
            cs+=a[i];
            if(cs>cm)
                cm=cs;
            if(cs<0)
                cs=0;
            ans=max(ans,cm+ltr[i-1]);
        }
        printf("%lld\n",ans);
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注