「POJ2362」Square
Description
Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?
Input
The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick – an integer between 1 and 10,000.
Output
For each case, output a line containing “yes” if is is possible to form a square; otherwise output “no”.
Sample Input
|
1 2 3 4 |
3 4 1 1 1 1 5 10 20 30 40 50 8 1 7 2 6 4 4 3 5 |
Sample Output
|
1 2 3 |
yes no yes |
题解
搜索+剪枝
倒序排序缩小搜索树
当前长度加上最小长度大于边长，返回
某长度不能完成某个子问题,和它一样长的也不能完成。
其实不加剪枝似乎也行
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<map> #include<cmath> #define inf 1000000000 #define pa pair<int,int> #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,n; int ave,mx,mn; int a[105]; bool sel[105]; bool dfs(int x,int num,int tot) { if(tot==ave)num++,tot=x=0; if(mn+tot>ave)return 0; if(num==3)return 1; int last=-1; for(int i=x+1;i<=n;i++) if(!sel[i]) { if(a[i]==last)continue; sel[i]=1; if(dfs(i,num,tot+a[i]))return 1; sel[i]=0; last=a[i]; } return 0; } int main() { T=read(); while(T--) { ave=mx=0;mn=inf; memset(sel,0,sizeof(sel)); n=read(); for(int i=1;i<=n;i++) a[i]=read(); sort(a+1,a+n+1,greater<int>()); for(int i=1;i<=n;i++) { ave+=a[i];mx=max(mx,a[i]); mn=min(mn,a[i]); } if(ave%4){puts("no");continue;} ave/=4; if(mx>ave){puts("no");continue;} sel[1]=1; if(dfs(1,0,a[1]))puts("yes"); else puts("no"); } return 0; } |
Subscribe
计数器 9852056
OI 课件=>
OI 课件=>