首页 > 代码库 > rqnoj 奥运火炬到厦门
rqnoj 奥运火炬到厦门
题目描述
背景:5月12日，在厦门人民的热烈欢迎下，象征着和平、友谊、圣洁的奥运火炬终于来到了厦门，开始了传递……
描述：厦门市市长宣布：“要把这次火炬接力办的很有意义。”“有意义”是什么意思呢？厦门市市长别出心裁地给它下了个定义：每个火炬手都有个意义值，可以将他们顺次看作一个首尾相接的环，而整个火炬接力的意义值是这个环的最大和连续子串。
比如： 串是 -2 2 0 1 -48 1，显然其最大和连续子串是2 0 1，其和是3。
现在给定n个火炬手的意义值，请算出整个火炬接力的意义值（意义值可能为负数）
输入格式
第1行一个整数n(1<=n<=1000000)表示n个火炬手
第2行有n个整数，每个整数都在longint的范围内。
新备注:因为未知原因，导致正常程序在测评8 9 10三个测试点时TLE，所以本题暂时关闭后3个测试点。数据范围改为5000
输出格式
火炬接力的意义值。
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cmath>#include<algorithm>#include<cstdlib>using namespace std;#define maxn 5000long a[2*(maxn+1)],ans;int main(){ long n; cin>>n; for (long i=1;i<=n;++i){ cin>>a[i]; if (a[i]<0) ++ans; } if (ans==n){ ans=-0x3fff; for (long i=1;i<=n;++i) if (a[i]>ans) ans=a[i]; } else{ ans=0; for (long i=1;i<=n;++i) a[i+n]=a[i]; for (long start=1;start<=n;++start){ long temp=0; for (long i=start;i-start+1<=n;++i){ if (temp+a[i]<0) temp=0; else temp+=a[i]; if (temp>ans) ans=temp; } } } cout<<ans<<endl; return 0;}
rqnoj 奥运火炬到厦门
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。