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

Re:sticks

Posted by jiangzhu at 2007-08-27 09:20:26 on Problem 1011
In Reply To:sticks Posted by:xiaomi at 2003-11-25 23:09:44
> 把给定的sticks按长度由大到小排序
> 先计算出能拼出多少根,然后一根一根的拼,我做了两个函数互相调用
> 一个是拼下一根,一个是选择一段合适的stick进行填充
> void judge(int use)
> { 
> 	if (use==sticks) //全部拼成
> 	{
> 		flag=1;
> 		return ;
> 	}
> 	for (int i=n-1;i>=0;i--)
> 		if (!d[i]) //stick是否已用过
> 			break;
> 	d[i]=1;
> 	create(p-c[i],use,i); //用没用过的最长的stick来拼下一根
> 	d[i]=0;
> } 
> void create(int q,int use,int next)
> {
> 	if (flag)
> 		return ;
> 	if (!q)
> 	{
> 		judge(use+1); //如果剩余长度为0,拼下一根
> 		return ;
> 	}
> 	for (int i=next;i>=0;i--) 
> 		if (!d[i]&&q>=c[i]) //如果没用过,并且比剩余长度短
> 		{ 
> 			d[i]=1;                 
> 			create(q-c[i],use,i+1); //填充
> 			d[i]=0; 
> 			if (flag)
> 				return ;
> 			if (c[i]==q)
> 				return ; //如果剩余部分正好等于
>                                              //某stick的长度,则不需要
>                                              //用较短的stick进行填充
> 		} 
> } 
这个算法好像不正确吧?下面这段应该要去掉的
if (c[i]==q)
return ; //如果剩余部分正好等于
         //某stick的长度,则不需要
         //用较短的stick进行填充

但是去掉就TLE了
不去掉又是WA
郁闷!!!

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