hdu1518深搜DFS

看队友ac了这个。。加上很久没写过深搜了。。手痒了。。遂拿之解闷~~

一开始超时。。玩命的超时（这次用的printf了）。。查之发现二逼了代码在已经搜过的位置重复搜了几次。。导致代码目测时间复杂度为o（n！）。。玩命啊。。改之。。wa。。顿时想起以前做过之一题目。。即在搜索过程中搜不成功还得回溯。。遂改方法。。ac~

#include<iostream> #include<algorithm> using namespace std; const int MAXM=22; int m; int num[MAXM]; bool vis[MAXM]; bool cmp(int a,int b) {return a>b; } bool dfs(int remd,int pos,int count,int len) {int i;if(count==4){return 1;}for(i=pos;i<=m-1;i++){if((!vis[i])&&remd>=num[i]){vis[i]=1;remd=remd-num[i];if(remd==0&&dfs(len,0,count+1,len)){return 1;}else if(dfs(remd,i+1,count,len)){return 1;}remd=remd+num[i];vis[i]=0;}}return 0; }int main() {int t;scanf("%d",&t);while(t--){int i;memset(vis,0,sizeof(vis));int sum=0;scanf("%d",&m);for(i=0;i<=m-1;i++){scanf("%d",&num[i]);sum+=num[i];}if(sum%4){printf("no\n");continue;}sort(num,num+m,cmp);if(sum/4<num[0]){printf("no\n");continue;}if(dfs(sum/4,0,0,sum/4)){printf("yes\n");}else{printf("no\n");}}return 0; }

　　

转载于:https://www.cnblogs.com/cj695/archive/2012/08/02/2620258.html

总结

以上是生活随笔为你收集整理的hdu1518深搜DFS的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。