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 731371663 at 2011-01-20 15:04:38 on Problem 3257
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX=10005;
int dp[1001][1001];//dp[i][j]表示在i点花费j美金的最大快乐值
struct node
{
	int x,w,f,c;
}a[MAX];

bool operator <(const node &a,const node &b)
{
	return a.x<b.x;//将所有材料按照起点升序排序
}

int main()
{
	//freopen("in.txt","r",stdin);
	int L,N,B;
	int i,j;
	scanf("%d%d%d",&L,&N,&B);
	for(i=0;i<N;i++)
	{
		scanf("%d%d%d%d",&a[i].x,&a[i].w,&a[i].f,&a[i].c);
	}
	sort(a,a+N);
	memset(dp,-1,sizeof(dp));
	for(i=0;i<=B;i++)
		dp[0][i]=0;//从0开始
	for(i=0;i<N;i++)
	{
		for(j=0;j<B;j++)
		{
			if(dp[a[i].x][j]==-1||a[i].c+j>B||a[i].x+a[i].w>L) continue;//dp[a[i].x][j]==-1表示无法到达a[i].x
			if(dp[a[i].x+a[i].w][j+a[i].c]<dp[a[i].x][j]+a[i].f)
				dp[a[i].x+a[i].w][j+a[i].c]=dp[a[i].x][j]+a[i].f;
		}
	}
   	printf("%d\n",dp[L][B]);
	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