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

能不能哪位大神帮我看下这段代码超时的原因?

Posted by 547880119 at 2010-04-10 22:54:58 on Problem 2355
/*
谢谢了!
*/

//poj 2355

//dp 由前向后dp

#include <iostream>
#include <limits>
#include <algorithm>
using namespace std;

const int MAX = 10005;

#define MIN(a,b) ((a)<(b))?(a):(b)

int d[MAX];

int L1,L2,L3,C1,C2,C3;
int N;
int start, end;

int dp[MAX];

int main()
{
	//memset(dp,0x7F,sizeof(dp));

	

	scanf("%d %d %d %d %d %d",&L1, &L2, &L3, &C1, &C2, &C3);
	scanf("%d",&N);
	scanf("%d %d",&start,&end);

	int t1=start, t2 = end;

	start = min(t1,t2);
	end = max(t1,t2);

	d[1] = 0;

	for(int i = 2; i <= N; i++)
		scanf("%d",&d[i]);
	
	//for(int i = start+1; i <= end; i++)
	//	dp[i] = 0x7F;

	for(int i = 1; i <= N; i++) dp[i] = INT_MAX;
	dp[start] = 0;
	
	for(int i = start; i <= end; i++)
	{
		for(int j = start+1; j <= end; j++)
		{
			int dis = d[j]-d[i];
			if(dis<=L1)
			{
				dp[j] = MIN(dp[j],dp[i]+C1);	
			}
			else if(dis<=L2)
			{
				dp[j] = MIN(dp[j],dp[i]+C2);
			}
			else if(dis<=L3)
			{
				dp[j] = MIN(dp[j],dp[i]+C3);
			}
			else
			{
				break;
			}
		}
	}	

	printf("%d\n",dp[end]);

	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