Square
Time Limit: 5000 ms Memory Limit: 65536 KB
Total Submit: 94 Accepted: 31
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 10000.
4≤M≤20, the number of sticks. M integers follow; each gives the length of a stick - an integer
between 1 and 10000.
Output
For each case, output a line containing "yes" if is is possible to form a square; otherwise output "no".
Sample Input
3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5
Sample Output
yes
no
yes
no
yes
这个总的来说还是比较简单的一题，由于我校oj数据较少，不怎么剪枝也能过，下面分别贴一下我最早写的麻烦代码和优化过的代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int sum,b,ok;
int a[22];
bool v[22];
int n;
bool pai(int a,int b)
{
return a>b;
}
void go(int d,int bs,int c)
{
if(bs==3)
{
ok=1;
return ;
}
if(ok==0)
{
for(int i=d;i<n;i++)
{
if(v[i])continue;
if(c+a[i]<=b&&!v[i])
{
v[i]=1;
if(c+a[i]==b)go(0,bs+1,0);
else go(i+1,bs,c+a[i]);
}
v[i]=0;
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
sum=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
if(sum%4!=0)
{
cout<<"no"<<endl;
continue;
}
b=sum/4;
sort(a,a+n,pai);
if(a[0]>b)
{
cout<<"no"<<endl;
continue;
}
memset(v,0,sizeof(v));
ok=0;
go(0,0,0);
if(ok)cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int sum,b,ok;
int a[22];
bool v[22];
int n;
bool pai(int a,int b)
{
return a>b;
}
bool go(int d,int bs,int c)
{
if(bs==3)
{
return true;
}
for(int i=d; i<n; i++)
{
if(v[i]||(i&&v[i-1]==0&&a[i]==a[i-1]))continue;
if(c+a[i]==b)
{
v[i]=1;
if(go(0,bs+1,0))return true;
v[i]=0;
return false;
}
else if(c+a[i]<b)
{
v[i]=1;
if(go(i+1,bs,c+a[i]))return true;
v[i]=0;
if(c==0)return false;
}
}
return false;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
sum=0;
scanf("%d",&n);
for(int i=0; i<n; i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
if(sum%4!=0)
{
cout<<"no"<<endl;
continue;
}
b=sum/4;
sort(a,a+n,pai);
if(a[0]>b)
{
cout<<"no"<<endl;
continue;
}
memset(v,0,sizeof(v));
if(go(0,0,0))cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
return 0;
}
第一个在我校oj上是50ms，第二个3ms