HDU-5280
Senior's Array
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 852 Accepted Submission(s): 311
But as is known to all, Xuejiejie is used to pursuing perfection. She wants to get a more beautiful interval. So she asks Mini-Sun for help. Mini-Sun is a magician, but he is busy reviewing calculus. So he tells Xuejiejie that he can just help her change one value of the element of A to P . Xuejiejie plans to come to see him in tomorrow morning.
Unluckily, Xuejiejie oversleeps. Now up to you to help her make the decision which one should be changed(You must change one element).
In each case, the first line contains two integers n and P. n means the number of elements of the array. P means the value Mini-Sun can change to.
The next line contains the original array.
1≤n≤1000, −109≤A[i],P≤109。
2
3 5
1 -1 2
3 -2
1 -1 2
/**
题意:给出一个数组,如果用p代替数组中的一个数求最大的区间和
做法:dp(比赛的时候想得太多)
**/
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#define maxn 1100
#define INF 0x7fffffff
using namespace std;
long long mmap[maxn];
long long dp[][maxn];
long long n;
long long DP()
{
dp[][] = max((long long),mmap[]);
for(int i=;i<n;i++)
{
dp[][i] = max((long long),dp[][i-] + mmap[i]);
}
long long tmp = mmap[];
for(int i=;i<n;i++)
{
dp[][i] = dp[][i-] + mmap[i];
tmp = max(tmp,dp[][i]);
}
return tmp;
}
int main()
{
//#ifndef ONLINE_JUDGE
// freopen("in.txt","r",stdin);
//#endif // ONLINE_JUDGE
int T;
scanf("%d",&T);
while(T--)
{
long long p;
scanf("%lld %lld",&n,&p);
for(int i=;i<n;i++)
{
scanf("%lld",&mmap[i]);
}
memset(dp,,sizeof(dp));
long long res = -INF;
for(int i=;i<n;i++)
{
long long tt = mmap[i];
mmap[i] = p;
res = max(res,DP());
mmap[i] = tt;
}
printf("%lld\n",res);
}
return ;
}
最新文章
- 获取ICommand的图片
- loj 1063(求割点个数)
- Python OpenCV —— Border
- lambda表达式、内置函数、进制和文件操作
- Swift UI开发初探
- (大数据工程师学习路径)第一步 Linux 基础入门----基本概念及操作
- [学习OpenCV攻略][012][读取、修改、保存图像]
- win7开启wifi
- Zookeeper实现master选举
- 使用abcpdf分页设置的问题
- __x__(11)0906第三天__图片标签
- 新的尝试!ComponentOne WinForm 和 .NET Core 3.0
- 全面理解虚拟DOM(1)
- Linq(高级查询)
- POI Sax 事件驱动解析Excel2003文件
- CentOS 6.5使用Corosync + pacemaker实现httpd服务的高可用
- 谈谈你对Java面向对象的理解
- ABAP-增强-层级BOM-AB件业务
- 【开发者笔记】c# 调用java代码
- 前端开发之jQuery篇--选择器