Senior's Array

Accepts: 199

Submissions: 944

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

问题描述

某天学姐姐得到了一个数组A，在这个数组的所有非空区间中，她找出了一个区间和最大的，并把这个区间和定义为这个数组的美丽值。

但是她觉得这个数组不够美，于是决定修理一下这个数组。

学姐姐将会进行一次操作，把原数组中的某个数修改为P（必须修改）。

最后她想使得修改后的数组尽可能美丽。请你帮助她计算经过修理后，这个数组的美丽值最大能是多少？

输入描述

第一行包含一个整数T，表示测试数据组数。

对于每组测试数据：

第一行包含两个整数n，P，表示数组长度以及修改后的值。

接下来一行包含n个整数A[i]，表示初始的数组。

1≤n≤1000, −109≤A[i],P≤109。

输出描述

对于每组测试数据输出一个整数表示对应的答案。

输入样例

输出样例

8

2

一个一个替换，看哪一次得到的最多。这道题比的时候被hack了，不开心啊啊啊啊。自己还是需要很大的努力。

还有要记住啊，这个是要一个一个替换，肯定是一个一个替换，没有大小条件啊，因为是序列啊啊啊。

代码：

#include <iostream>

#include <string>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

int value[1005];

long long left_v[1005];

long long max(long long a,int b)

{

	return a>b?a:b;

}

int main()

{

	int Test,num,tihuan,i,j,temp;

	long long ans;

	scanf("%d",&Test);

	while(Test--)

	{

		ans=-1e18;

		memset(left_v,0,sizeof(left_v));

		scanf("%d%d",&num,&tihuan);

		for(i=1;i<=num;i++)

		{

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

		}

		for(j=1;j<=num;j++)

		{

			temp=value[j];

			value[j]=tihuan;

			left_v[1]=value[1];

			if(left_v[1]>ans)

				ans=left_v[1];

			for(i=2;i<=num;i++)

			{

				left_v[i]=max(left_v[i-1]+value[i],value[i]);

				if(left_v[i]>ans)

					ans=left_v[i];

			}

			value[j]=temp;

		}

		cout<<ans<<endl;

	}

	return 0;

}

65536

HDU 5280 BestCoder Round #47 1001：Senior's Array

Senior's Array