有 n 根木棍，现在这些木棍不允许切割，但是可以头尾拼接在一起，在全部用完的情况下请问能否组成一个等边三角形? 输入格式 输入一个整数 n 表示有 n 根木棍 (n<=20) 接下来 n 个数字 ai 分别表示每根木棍的长度 (ai<=10000) 输出格式 若能则输出 yes 否则输出 no 样例 输入数据 1 5 1 2 3 4 5 输出数据 1 yes
#pragma GCC optimize(2,3,"Ofast") #include<bits/stdc++.h> using namespace std; const int MAXN=1e5+5; int n,sum,a[MAXN]; bool flag[MAXN]; void dfs(int x,int y,int cnt){ if(y>sum/3) return; if(y==sum/3){ y=0; cnt++; } if(x==n+1){ if(cnt==3){ puts("yes"); exit(0); } return; } for(int i=1;i<=n;i++){ if(!flag[i]){ flag[i]=1; dfs(x+1,y+a[i],cnt); flag[i]=0; } } } signed main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i]; dfs(1,0,0); puts("no"); return 0; }
#pragma GCC optimize(2,3,"Ofast") #include<bits/stdc++.h> using namespace std; const int MAXN=1e5+5; int n,sum,cnt,a[MAXN]; bool flag[MAXN]; void dfs(int x,int y){ if(y>sum/3) return; if(y==sum/3){ y=0; cnt++; } if(x==n+1){ if(cnt==3){ puts("yes"); exit(0); } return; } for(int i=1;i<=n;i++){ if(!flag[i]){ flag[i]=1; dfs(x+1,y+a[i]); flag[i]=0; } } } signed main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i]; dfs(1,0); puts("no"); return 0; }
共 2 条回复