| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:搜索题,讲究的就是搜索顺序,剪枝等技巧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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator