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

处女贴纪念50水题~采用一维数组,每次更新为最新一行的最优解,这样能省不少内存空间

Posted by xiaoye51888 at 2010-10-09 15:15:33 on Problem 3176
7721941 xiaoye51888 3176 Accepted 732K 204MS C++ 468B 2010-10-09 14:52:18 
7722034 xiaoye51888 3176 Accepted 248K 172MS C++ 421B 2010-10-09 15:08:13

#include <iostream>
using namespace std;
#define N 351 
int a[N+2];

int main()
{
	int n,i,j,t,k;
	cin>>n;
	cin>>a[0];
	for(i=1;i<n;++i)
	{
		cin>>t;
		k=a[0];
		a[0]+=t;
		for(j=1;j<i;++j)
		{
			cin>>t;
			if(k>a[j]) t+=k;
			else t+=a[j];
			k=a[j];
			a[j]=t;
		}
		cin>>t;
		a[i]=k+t;
		
	}

	
	t=a[0];
	for(i=1;i<=n;++i)
	{
		if(t<a[i]) t=a[i];

	}
	cout<<t<<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