这题 个人只剪了两次,一是如果所有的长度和对4取余,若不为0,则剪去;
还有是如果有一个长度大于总长的4分之1,剪去;
#include<stdio.h> #include<string.h> #include<stdlib.h> int vis[30],s[30]; int flag; int b,r,l; void dfs(int bian,int l,int k)//深搜 { int i; if(bian==5) { flag=1; return ; } if(l==r) { dfs(bian+1,0,0); if(flag) return ; } for(i=k;i<b;i++) { if(!vis[i]&&l+s[i]<=r) { vis[i]=1; dfs(bian,s[i]+l,i+1); if(flag) return ; vis[i]=0; } } } int main() { int a; scanf("%d",&a); while(a--) { int i,j=0; r=0; scanf("%d",&b); for(i=0;i<b;i++) { scanf("%d",&s[i]); r=r+s[i]; } if(r%4!=0) { printf("no\n"); continue; } else { r=r/4; for(i=0;i<b;i++) { if(s[i]>r) { printf("no\n");j=1;} } if(j==1) continue; } memset(vis,0,sizeof(vis)); flag=0; dfs(1,0,0); if(flag) printf("yes\n"); else printf("no\n"); } return 0; }
<pre name="code" class="cpp">#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; int a[30]; bool vis[30]; int n,m,sum,len; bool dfs(int cur,int time ,int k) { if(time==3) return true; for(int i=k; i>=1; i--) { if(!vis[i]){ vis[i]=true; if(cur+a[i]==len){ if(dfs(0,time+1,m)) return true; } else if(cur+a[i]<len){ if(dfs(cur+a[i],time,i-1)) return true; //关键是i-1..不然会一直超时的。。 } vis[i]=false; } } return false; } int main() { scanf("%d",&n); while(n--) { scanf("%d",&m); sum=0; for(int i=1; i<=m; i++) { scanf("%d",&a[i]); sum+=a[i]; } memset(vis,0,sizeof(vis)); sort(a,a+m); if(sum%4==0&&a[m]<=sum/4&&m>=4) { len=sum/4; if(dfs(0,0,m)) printf("yes\n"); else printf("no\n"); } else printf("no\n"); } return 0; }