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

时间o(n*n) ,空间o(n)

Posted by lzqxh at 2011-09-15 00:33:08 on Problem 1036
表示实在无法理解怎么可能内存不够。。
先对n个人按时间排序
dp[i]表示第i个人成功进步得到的最高分。。。注意是成功!
那则必然从dp[j]转移过来的 。。0<=j <i
然后没了。。

#include<cstdio>
#include<algorithm>

using namespace std; 

struct gangster{	int t , s ,p;
}a[105];
int dp[105],n,k,t;
bool cmp( gangster a , gangster b ){	return a.t < b.t;}

int main()
{
	scanf("%d%d%d",&n,&k,&t);
	a[0].t = a[0].s = a[0].p = 0;
	for (int i = 1; i<=n; i++) scanf("%d",&a[i].t );
	for (int i = 1; i<=n; i++) scanf("%d",&a[i].p ); 
	for (int i = 1; i<=n; i++) scanf("%d",&a[i].s ); 
	sort( a , a+n+1 , cmp );
	int ans = 0;
	for (int i = 1; i<=n; i++)
	{
		if ( a[i].t > t ) break;
		for (int j = 0; j<i; j++)
		{
			if ( dp[j] == 0 && j!= 0 ) continue; 
			if ( abs( a[i].t - a[j].t ) < abs( a[i].s - a[j].s ) ) continue;
			dp[i] = max ( dp[i] , dp[j] + a[i].p );
		}
		ans = max( ans , dp[i] );
	}
	printf("%d\n",ans);
	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