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