Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 13374 Accepted Submission(s): 4244
#include <cstdio> #include <cstring> #include <queue> #include <algorithm> #include <stdlib.h> using namespace std; int v[25]; int n; int sum = 0; bool vis[25]; bool flag; //cnt代表当前到第几根了,len代表当前木棍长度 void dfs(int cnt,int len,int now){ if(cnt==4){ flag = true; return; } for(int i=now;i<n;i++){ if(flag) return; if(vis[i]||sum<len+v[i]) continue; if(sum==len+v[i]){ vis[i] = true; dfs(cnt+1,0,0); vis[i] = false; }else if(sum>len+v[i]){ vis[i] = true; dfs(cnt,len+v[i],i+1); vis[i] = false; } } } int cmp(int a,int b){ return a>b; } int main(){ int tcase; scanf("%d",&tcase); while(tcase--){ scanf("%d",&n); sum = 0; for(int i=0;i<n;i++){ scanf("%d",&v[i]); sum+=v[i]; } sort(v,v+n,cmp); if(sum%4!=0){ printf("no\n"); continue; } sum/=4; if(v[0]>sum) { printf("no\n"); continue; } memset(vis,false,sizeof(vis)); flag = false; dfs(0,0,0); if(flag) printf("yes\n"); else printf("no\n"); } }
原文:http://www.cnblogs.com/liyinggang/p/5740427.html