Sum-（最大子序列和）

http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=652&pid=1003

题目大意：

给你一个序列，你随便找一个区间，让这个区间的所有数都变成f(x)=(1890*x+143)%10007

然后在求和问最大的和是多少

分析：

可以把每一个x的f[x]都求出来让他们的差保存到b[N]中求b[N]的最大子序列和

然后让刚开始序列的总和加上这个最大子序列和就是最大的和

补充：

求最大子序列和

int maxsublinear(const int a[], int n)

{

    int i;

    int curSum = ; /* 当前序列和 */

    int maxSum = ; /* 最大序列和 */

    int begin = end = ;

    /* 开始循环求子序列和 */

    for (i = ; i < n; i++)

    {

        curSum = curSum + a[i];

        /* 与最大子序列和比较，更新最大子序列和 */

        if (curSum > maxSum)

        {

            maxSum = curSum;

            end = i;

        }

        /* 动态规划部分，舍弃当前和为负的子序列 */

        if (curSum < )

        {

            curSum = ;

            begin = i +  >= n ? i : i + ;

        }

    }

    return maxSum;

}

上代码：

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<stdlib.h>

#include<algorithm>

#include<iostream>

using namespace std;

#define N 110010

int n,a[N],i,f[N],b[N];

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        memset(a,,sizeof(a));

        memset(f,,sizeof(f));

        memset(b,,sizeof(b));

        int s=;

        for(i=;i<n;i++)

        {

            scanf("%d",&a[i]);

            s+=a[i];

            f[i]=(*a[i]+)%;

            b[i]=f[i]-a[i];

        }

        int Max=,sum=;

        for(i=;i<n;i++)

        {

            sum+=b[i];

            if(Max<sum)

            {

                Max=sum;

            }

            if(sum<)

                sum=;

        }

        printf("%d\n",s+Max);

    }

    return ;

}

巴特西

Sum-（最大子序列和）

最新文章

热门文章