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

DP附代码。。

Posted by lulyon at 2011-03-14 00:41:35 on Problem 2479 and last updated at 2011-03-14 00:41:59
从两端分别求以i为尾的最大连续子段和。然后把两端子段和相加求其最大值。。

#include<iostream>
using namespace std;

int a[50010];
int b[50010];
int c[50010];

int main(){
	int n,t;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1; i<=n; ++i){
			scanf("%d",a+i);
		}
		
		for(int i=1; i<=n; ++i){
			if(i==1){
				b[i]=a[i];
			}
			else{
				if(b[i-1]>0){
					b[i] = a[i]+b[i-1];
				}
				else{
					b[i]=a[i];
				}
			}
		}
		
		for(int i=2;i<=n; ++i){
			if(b[i]<b[i-1])b[i]=b[i-1];
		}
		
		for(int i=n; i>=1; --i){
			if(i==n)c[i]=a[i];
			else{
				if(c[i+1]>0){
					c[i]=c[i+1]+a[i];
				}
				else{
					c[i]=a[i];
				}
			}
		}
		
		for(int i=n-1; i>=1; --i){
			if(c[i]<c[i+1])c[i]=c[i+1];
		}
		
		int max=b[1]+c[2];
		for(int i=2; i+1<=n; ++i){
			if(max<b[i]+c[i+1])max=b[i]+c[i+1];
		}
		printf("%d\n",max);
	}
	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