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:用动态规划,就是n^3

Posted by seu_enic at 2009-03-02 19:00:05 on Problem 1050
In Reply To:用动态规划,就是n^3 Posted by:gfedcba at 2009-02-27 17:59:13
> #include <iostream>
> using namespace std;
> short MaxSum(short *colSum, int n)
> {
> 	int maxSum = 0;
> 	int b=0;
> 	int i=0;
> 	for (i; i<=n-1; i++)
> 	{
> 		if (b>0)
> 		{
> 			b+=colSum[i];
> 		}
> 		else
> 		{
> 			b = colSum[i];
> 		}
> 		if (b > maxSum)
> 		{
> 			maxSum = b;
> 		}
> 	}
> 	return maxSum;
> }
> 
> 
> int main()
> {
>     const short N = 100;
> 	short matrix[N][N];
> 	short colSum[N]={0};
> 
> 	int i,j,k;
> 	int n;
> 	cin>>n;
> 	
>     for (i=0; i<=n-1; i++)
> 	{
> 		for (j=0; j<=n-1; j++)
> 		{
> 			cin>>matrix[i][j];
> 		}	
> 	}
> 
> 
> 	int maxSubSum = 0;
> 	for (i=0; i<=n-1; i++)
> 	{
> 		for (k=0; k<=n-1; k++)
> 		{
> 			colSum[k] = 0;
> 		}
> 		for (j=i; j<=n-1; j++)
> 		{
> 			int maxTemp;
> 			for (k=0; k<=n-1; k++)
> 			{
> 				colSum[k] += matrix[j][k];
> 			}
> 			maxTemp = MaxSum(colSum, n);
> 			if (maxTemp > maxSubSum)
> 			{
> 				maxSubSum = maxTemp;
> 			}
> 		}
> 	}
> 
> 	cout<<maxSubSum<<endl;
>     return 0;
> }

我就是问为什么这个程序是O(n^3)的。。。我也是这样写的。。。

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