Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:我用的是最大子段和 DP 还是WA 不知道错哪里了

Posted by acme at 2005-09-18 15:20:52 on Problem 2479
In Reply To:我用的是最大子段和 DP 还是WA 不知道错哪里了 Posted by:y_zou at 2005-08-21 13:03:37
当输入两个数时,就错了。
输入:
1
2
-1 -2
输出为-1???
> /*
> 	name: Maximum sum
> 	author: Y_zou
> 	time: 2005_8_21	
> */
> 
> #include <iostream>
> #include <cstdio>
> 
> using namespace std;
> int arrayB[50001];
> int arrayC[50001];
> 
> int MaxSum(int cnt,int* buff)
> {
> 	if(cnt<2)
> 		return 0;
> 	
> 	arrayB[0] = 0;
> 	arrayC[1] = 0;
> 	for(int i=1;i <= 2; i++)
> 	{
> 		arrayB[i] = arrayB[i-1] + buff[i];
> 		arrayC[i-1] = arrayB[i];
> 		int max = arrayB[i];
> 		for(int j=i+1; j<=i+cnt-2; j++)
> 		{
> 			arrayB[j] = arrayB[j-1] > arrayC[j-1] ? arrayB[j-1]+ buff[j] : arrayC[j-1] + buff[j];
> 			arrayC[j-1] = max;
> 			if(max < arrayB[j])
> 				max = arrayB[j];
> 		}
> 		arrayC[i+cnt-2] = max;
> 	}
> 	int sum = 0;
> 	for(int c=2; c<=cnt; c++)
> 	{
> 		if(sum < arrayB[c])
> 			sum = arrayB[c];
> 	}
> 	return sum;
> 
> 
> }
> int main()
> {
> 	int Case,cnt;
> 	int i;
> 	int buff[50001];
> 
> 	scanf("%d",&Case);
> 	for(int c=0; c <Case; c++)
> 	{
> 		if(c)
> 			cout << endl;
> 		scanf("%d", &cnt);
> 		for(i=1; i <= cnt; i++)
> 		{
> 			scanf("%d",&buff[i]);
> 		}
> 		int sum = 0;
> 
> 		if(cnt==2)
> 		{
> 			sum =  buff[1] + buff[2];
> 			if(sum > buff[1] && sum > buff[2])
> 				cout << sum << endl;
> 			else
> 			{
> 				if(buff[1] > buff[2])
> 					cout << buff[1] << endl;
> 				else
> 					cout << buff[2] << endl;
> 			}
> 		}
> 		else
> 	 		cout << MaxSum(cnt, buff) << endl;
> 	}
> 
> 	return 0;
> }
> 

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator