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

用动态规划做,说超空间。。。汗,显然没用到10M内存啊

Posted by yzhw at 2008-11-13 17:38:29 on Problem 1062
如题,郁闷中
# include <stdio.h>
int refer[101];
int limit;
typedef struct member
{
	int money;
	int dengji;
	int num_d;
	int tidai[101][2];
}member;
member data[101];
int deal(int num)
{
  if(refer[num]!=-1) return refer[num];
  else if(data[1].dengji-data[num].dengji>limit) return 99999;
  else
  {
	  if(data[num].num_d==0) return data[num].money;
	  else 
	  {
		 int i;
		 int result=data[num].money;
		 for(i=1;i<=data[num].num_d;i++)
		 {
			 if(deal(data[num].tidai[i][0])+data[num].tidai[i][1]<result)
                 result=deal(data[num].tidai[i][0])+data[num].tidai[i][1];
		 }
		 refer[num]=result;
		 return result;
	  }
  }
}
		  
int main()
{
   int i,result;
   int num;
   memset(refer,-1,sizeof(refer));
   scanf("%d %d",&limit,&num);
   for(i=1;i<=num;i++)
   {
	int j;
    scanf("%d %d %d",&data[i].money,&data[i].dengji,&data[i].num_d);
	for(j=1;j<=data[i].num_d;j++)
	{
	 scanf("%d %d",&data[i].tidai[j][0],&data[i].tidai[j][1]);
	}
   }
   result=deal(1);
   printf("%d\n",result);
   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