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

一维Dp不就好了嘛……

Posted by 1000010314 at 2013-02-21 18:41:31 on Problem 1036
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

int N,K,T,width=0,data[101],ans=0;

bool visit[101];

struct Ganster
{
	int t,p,s;
};

Ganster g[101];

inline bool operator<(const Ganster & g1, const Ganster & g2)
{
	return g1.t==g2.t ? (g1.s==g2.s ? g1.p<g2.p : g1.s<g2.s) : g1.t<g2.t;
}

int main()
{
	scanf("%d%d%d",&N,&K,&T);
	g[0].t=g[0].s=g[0].p=-1;visit[0]=true;
	for(int i=1;i<=N;i++){scanf("%d",&g[i].t);}
	for(int i=1;i<=N;i++){scanf("%d",&g[i].p);}
	for(int i=1;i<=N;i++){scanf("%d",&g[i].s);}
	sort(g,g+N+1);g[0].t=g[0].s=g[0].p=data[0]=0;
	for(int i=1;i<=N;i++)
	{
		for(int j=0;j<i;j++)
		{
			if(visit[j])
			{
				if(g[i].t-g[j].t>=abs(g[i].s-g[j].s))
				{
					data[i]=max(data[i],data[j]+g[i].p);
				}
			}
		}
		visit[i]=(bool)data[i];
		ans=max(ans,data[i]);
	}
	cout<<ans<<endl;
	system("pause");
	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