首页 > 代码库 > poj2362
poj2362
#include<iostream> using namespace std; int data[20]; int total; int rec; int n; int vis[20]; int flag; int flag1; void dfs(int step,int sum,int k) { if(step==3) //step为3时就可以退出了,因为前面三步都已经成功了,剩下的肯定能拼成 { flag1=1; return; } for(int i=k;i<n;i++) { if(sum+data[i]>rec) continue; if(vis[i]==0) { vis[i]=1; if(sum+data[i]<rec) { dfs(step,sum+data[i],i+1); if(flag1) //剪枝,上一个dfs回来后如果已经满足条件就不用向下进行了 return; } if(sum+data[i]==rec) { dfs(step+1,0,0); if(flag1) //剪枝,上一个dfs回来后如果已经满足条件就不用向下进行了 return; } vis[i]=0; } } return; } int main() { int case_num; //freopen("input.txt","r",stdin); cin>>case_num; for(int p=1;p<=case_num;p++) { total=0; cin>>n; for(int i=0;i<n;i++) { cin>>data[i]; total=total+data[i]; } if(total%4) { cout<<"no"<<endl; continue; } else rec=total/4; flag=0; for(int i=0;i<n;i++) { if(data[i]>rec) { flag=1; cout<<"no"<<endl; } break; } if(flag) continue; for(int i=0;i<n;i++) { for(int j=0;j<n-1-i;j++) { if(data[j]<data[j+1]) { int temp=data[j]; data[j]=data[j+1]; data[j+1]=temp; } } } for(int i=0;i<n;i++) vis[i]=0; flag1=0; dfs(0,0,0); if(flag1) cout<<"yes"<<endl; else cout<<"no"<<endl; } return 0; }
poj2362
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。