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

WA了好多次了。。。

Posted by juventus at 2010-07-15 20:00:42 on Problem 1036
//dp[i]表示以第i个结尾的所能得到的最大财产值,dp[i] = max(dp[j]+p_i) && T[i] - T[j] >= abs(S[i] - S[j]),数组已按时间排序

#include <iostream>
#include <cmath>

using namespace std;

#define MAXN 100
#define MAXK 100
#define MAXT 30000

int dp[MAXN + 1];

struct Gangster
{
	int T, P, S;
	Gangster(int tt = 0, int pp = 0, int ss = 0)
	{
		T = tt;
		P = pp;
		S = ss;
	}
};

Gangster gangster[MAXN + 1];

int MyCompare(const void * e1, const void * e2)
{
	return ((Gangster *)e1)->T - ((Gangster *)e2)->T;
}

int main()
{
	int N, K, T;
	scanf("%d %d %d", &N, &K, &T);
	int i, j;
	for (i = 0; i < N; i++) scanf("%d", &gangster[i].T);
	for (i = 0; i < N; i++) scanf("%d", &gangster[i].P);
	for (i = 0; i < N; i++) scanf("%d", &gangster[i].S);
	qsort(gangster, N, sizeof(gangster[0]), MyCompare);
	if (gangster[0].S < gangster[0].T) dp[0] = gangster[0].P;
	else dp[0] = 0;
	for (i = 1; i < N; i++)
	{
		int tempmax = 0;
		bool flag = false;
		for (j = 0; j < i; j++)
		{
			if (dp[j] != 0)//j被用到了
			{
				if (gangster[i].T == gangster[j].T && gangster[i].S != gangster[j].S) continue;
				if (gangster[i].T - gangster[j].T >= abs(gangster[i].S - gangster[j].S + 0.0))
				{
					if (dp[j] + gangster[i].P > tempmax) tempmax = dp[j] + gangster[i].P;
				}
				flag = true;
			}
		}
		if (!flag)
		{
			if (gangster[i].S <= gangster[i].T) dp[i] = gangster[i].P;
			else dp[i] = 0;
		}
		else dp[i] = tempmax;
	}
	int ans = 0;
	for (i = 0; i < N; i++)
	{
		if (dp[i] > ans) 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