学步园

搜索经典题，与pku acm_1011题类似。

写得有点拗手，一开始都不知道跳到哪里去了，还得参考了很久以前做的1011题的源码，还得多多练习啊~

详细代码：

Problem: 2362 User: moxiaomomo<br /> Memory: 240K Time: 110MS<br /> Language: C++ Result: Accepted</p> <p>#include <iostream><br /> #include <algorithm><br /> using namespace std;<br /> int n,m, s[25],sum;<br /> bool mark[25];<br /> bool cmp(int a, int b){<br /> return a > b;<br /> }<br /> bool DFS(int cur_len, int k, int cur_num){<br /> if (cur_num == 4) return true; //4条边全部还原成功，返回true<br /> else if (cur_len == sum) return DFS(0, 0, cur_num + 1); //已完成当前一条边，还原下一条边<br /> else{<br /> int i;//pre,pre = 0,<br /> for (i = k; i < m; i++)<br /> {<br /> if (mark[i] && s[i] + cur_len <= sum){//当前木棍可用 //&& s[i] != pre<br /> //pre = s[i];<br /> mark[i] = false; //改变使用状态<br /> if (DFS(cur_len + s[i], i + 1, cur_num)) break; //递归检测下一条木棍<br /> mark[i] = true; //如果使用当前的木棍并不能成功还原的话，还原此木棍状态<br /> if (k == 0) return false; //回溯到第一根木棍仍然不能成功还原时，返回false<br /> }<br /> }<br /> if (i == m) return false; //一直到循环结束都无法还原边，则return false<br /> else return true;<br /> }<br /> }<br /> int main(){<br /> cin>>n;</p> <p> while(--n>=0)<br /> {<br /> cin>>m;<br /> for (int i = sum = 0; i < m; i++)<br /> {<br /> cin>>s[i];<br /> sum += s[i];<br /> }<br /> if(sum%4!=0)<br /> {printf("no/n");continue;}<br /> sort(s, s + m, cmp);<br /> sum /= 4;<br /> memset(mark, true, sizeof(mark));<br /> if(DFS(0, 0, 0))printf("yes/n");<br /> else printf("no/n");<br /> }<br /> return 0;<br /> }