| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
真心不明白为什么tle,有高手帮我看一下吗?#include<iostream>
#include<algorithm>
using namespace std;
int sticks[25], mark[25], side, M;
bool ok;
int comp(int a, int b)
{
return a > b;
}
void dfs(int cur, int left, int sideNum)
{
int i;
if(sideNum == 4)
{
ok = true;
return;
}
for(i = cur; i < M; i++)
{
if(mark[i] == 1)
continue;
if(i > 0)
{
if(sticks[i] == sticks[i-1] && mark[i-1] == 0)
continue;
}
if(left < sticks[i])
continue;
mark[i] = 1;
if(sticks[i] == left)
{
int temp;
for(temp = 0; mark[temp] == 1; temp++);
dfs(temp, side, sideNum+1);
}
else
dfs(cur+1, left-sticks[i], sideNum);
if(ok)
return;
mark[i] = 0;
if(left == sticks[i] || left == side)
return;
}
return;
}
int main()
{
int N, sum;
scanf("%d", &N);
while(N--)
{
scanf("%d", &M);
//init
sum = 0;
ok = false;
memset(mark, 0, sizeof(mark));
for(int i = 0; i < M; i++)
{
scanf("%d", &sticks[i]);
sum += sticks[i];
}
//枝剪1
if(sum % 4 != 0)
{
printf("no\n");
continue;
}
side = sum / 4;
//先进行排序再深搜
sort(sticks, sticks+M, comp);
//枝剪2
if(sticks[0] > side)
{
printf("no\n");
continue;
}
dfs(0, side, 0);
if(ok)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator