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:搜索题,讲究的就是搜索顺序,剪枝等技巧

Posted by wangcheng711 at 2004-02-22 14:49:40 on Problem 1011
In Reply To:搜索题,讲究的就是搜索顺序,剪枝等技巧 Posted by:hawk at 2004-02-22 11:37:33
我的搜索顺序是对的,剪枝也是对的,就是不过
我的算法和那些通过了的差不多,怎么我的就是不过了,能帮我看一下我的程序吗?
非常谢了!
#include <iostream.h>
int a[100], b[100];
int flag;
int length, n, sticks;
void search(int num, int now, int next);
void solve(int num)
{
	if (num>sticks) {flag = 1; cout<<length<<endl; return;}
	int i;
	for (i=1; i<=n; i++) if (!b[i]) break;
	b[i] = 1;
	search(num, a[i], i);
	b[i] = 0;
}

void search(int num, int now, int next)
{
	if (flag == 1) return;
	if (now == length) { solve(num+1); return;}
	if (next+1 > n) return;
	int i;
	for (i=next+1; i<=n; i++)
		if (!b[i] && (now+a[i]<=length))
		{	
			b[i] = 1; 
			search(num, now+a[i], i);
			b[i] = 0;
			if (flag == 1) return;
			if (now+a[i]==length) return;		
		}
}

void main()
{
	flag = 0;	
	a[0] = 0;
	cin>>n;	
	while (n!=0)
	{
		int total=0;
		for (int i=1; i<=n; i++)
		{
			cin>>a[i];
			b[i] = 0;
			total += a[i];
			int temp=a[i], j=i;
			while (temp<a[j-1]) {a[j] = a[j-1]; j--;}
			a[j] = temp;
		}		
		length = a[n];	
		for (length=a[n]; length<=total; length++)
		{
			if (total%length==0 && !flag)
			{
				sticks = total / length;
				solve(1);
			}							
		}
		flag = 0;
		cin>>n;
	}
}

> 并不是说只要会搜就可以

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