hdu1003 wa...

来源：蜘蛛抓取(WebSpider) 时间：2012-01-23 23:25 标签： hdu1003
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
下载作业帮安装包
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
hdu 1003 为啥WA诶?Problem DescriptionGiven a sequence a[1],a[2],a[3].a[n],your job is to calculate the max sum of a sub-sequence.For example,given (6,-1,5,4,-7),the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.InputThe first line of the input contains an integer T(1
边缘の0037
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
简单回答一下吧：给你一个例子 -5 1 2当加2之后pre小于0吧, if(pre < 0)
}这样必然让beg = i了是吧!实际上beg应该等于i-1吧这样一定会出错了吧!如果还是不懂的话,就给我留个言吧,我给你改改代码
扫描下载二维码Time Limit:
MS (Java/Others)&&&&Memory Limit:
K (Java/Others)Total Submission(s): 211310&&&&Accepted Submission(s):
Problem Description
Given a sequence a[1],a[2],a[3]......a[n], your job is
to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7),
the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
The first line of the input contains an integer
T(1&=T&=20) which means the number of test cases. Then T lines follow,
each line starts with a number N(1&=N&=100000), then N integers
followed(all the integers are between -1000 and 1000).
For each test case, you should output two lines. The
first line is "Case #:", # means the number of the test case. The second line
contains three integers, the Max Sum in the sequence, the start position of the
sub-sequence, the end position of the sub-sequence. If there are more than one
result, output the first one. Output a blank line between two cases.
Sample Input
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
Sample Output
解题心得：
　　这个题是一个简单地动态规划题，题意：输入n个数，求它的最大的子序列和。首先写出状态转移方程： sum[i]=max{sum[i-1]+a[i],a[i]}。
　　s数组是记录开始位置，每当sum加上一个a[i]，值小于0的时候，s取用新的值。ans是记录结束位置，每当sum加上一个a[i]，值大于等于0的时候，更新一下。
　 & 我又在格式问题上出错了，以后要更加注意格式问题，最后一行不需要换行！
　　也可以参考这个人的思路，，通过枚举发现的规律。
最后是代码：
#include &iostream&
#include &cstdio&
using namespace
int main()
int a[100005];//存储序列
int sum[100005];//存储以每个数为结尾的子序列和
int s[100005];//存储开始位置
int//结束位置
scanf("%d",&t);
for(int i=1;i&=t;i++){
scanf("%d",&n);
for(int i1=0;i1&n;i1++){
scanf("%d",&a[i1]);
sum[0]=a[0];
for(int j=1;j&n;j++){
if(sum[j-1]&=0){
sum[j]=sum[j-1]+a[j];
s[j]=s[j-1];
sum[j]=a[j];
if(sum[ans]&sum[j])
printf("Case %d:\n%d %d %d\n",i,sum[ans],s[ans]+1,ans+1);
printf("\n");
printf("Case %d:\n%d %d %d\n",i,sum[ans],s[ans]+1,ans+1);
阅读(...) 评论()7950人阅读
Time Limit:
MS (Java/Others)&&&&Memory Limit:
K (Java/Others)
Total Submission(s): 52833&&&&Accepted Submission(s): 11726
Problem Description
Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 &#43; (-1) &#43; 5 &#43; 4 = 14.
The first line of the input contains an integer T(1&=T&=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1&=N&=100000), then N integers followed(all the integers are between -1000 and
For each test case, you should output two lines. The first line is &Case #:&, # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end
position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.
Sample Input
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
Sample Output
#include &stdio.h&
int main()
{int n,T,a,sta,end,max,k,i,p,t;
scanf(&%d&,&T);
for(p=1;p&=T;p++) {
scanf(&%d&,&n);
max=-9999;
//因为一个数a 是-的，所以这里相当于变成最小值
//表示 某段连续和
sta=end=k=1;
// sta最大和的开始,end最大和的结束,k记录每次求和的开始
for(i=1;i&=n;i++) {
scanf(&%d&,&a);
if(t&max) {
//记录最大连续和的值
if(p!=1) printf(&/n&);
printf(&Case %d:/n&,p);
printf(&%d %d %d/n&,max,sta,end);
下面是用数组做的：
#include &stdio.h&
#include &string.h&
int a[100002];
int t,n,max,sum,l,r,i,j,k;
int main()
scanf(&%d&,&t);
for(i=1;i&=t;i++){
scanf(&%d&,&n);
bool pd=0;
sum=max=l=r=0;
for(j=1;j&=n;j++)
scanf(&%d&,a+j);
if(a[j]&0) pd=1;
sum+=a[j];
if(sum&0) sum=0,k=j+1;
if(sum&max) max=sum,l=k,r=j;
max=a[1],l=1,r=1;
for(j=2;j&=n;j++)
if(a[j]&max)
max=a[j],l=j,r=j;
printf(&Case %d:/n&,i);
printf(&%d %d %d/n&,max,l,r);
if(i&t) puts(&&);
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：244322次
排名：千里之外
原创：23篇
转载：22篇
评论：109条
(1)(1)(4)(6)(10)(1)(1)(3)(1)(2)(1)(1)(7)(1)(2)(24)日常训练（59）
每日一血First Blood（28）
题目链接&http://acm./showproblem.php?pid=1003
按照DP的思路写的，但是一直WA，后来看Discuss才知道有可能全是负数，这个时候DP会导致L和R都为N，max&#20540;也不对。于是在输入的时候进行了检测，AC。
代码&/Kiritow/OJ-Problems-Source/blob/master/HDOJ/1003.cpp
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：61363次
积分：2237
积分：2237
排名：第16963名
原创：150篇
转载：78篇
评论：19条
(10)(5)(2)(2)(1)(2)(4)(7)(11)(61)(21)(3)(24)(24)(27)(5)(6)(1)(6)(7)

我要回帖

更多关于 hdu1003 的文章

 

随机推荐