| ||||||||||
| 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 | |||||||||
求助高手帮忙看一下 论坛上的测试数据都过了 实在没办法了#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int sticks[22];
bool mark[22];
int length;
int num;
int flag;
int cmp(int a, int b){
return a > b;
}
void dfs(int begin, int sum, int step){
if(step == 3) {
flag = 1;
return;
}
if(flag == 1){
return;
}
int nsum;
for (int i = begin; i <= num; ++i) {
if(mark[i] == true) continue;
nsum = sum + sticks[i];
if(nsum > length) continue;
if(nsum == length){
mark[i] = true;
dfs(1, 0, step + 1);
mark[i] = false;
if(flag == 1){
return;
}
}
if(nsum < length){
mark[i] = true;
dfs(i + 1, nsum, step);
mark[i] = false;
if(flag == 1){
return;
}
}
}
}
int main(){
int n;
scanf("%d", &n);
while (n --){
memset(sticks, 0, sizeof(sticks));
memset(mark, false, sizeof(mark));
int sum = 0;
flag = 0;
scanf("%d", &num);
for (int i = 1; i <= num; ++i) {
scanf("%d", &sticks[i]);
sum += sticks[i];
}
sort(sticks + 1, sticks + num + 1, cmp);
length = sum / 4;
if( num < 4 ){
printf("no\n");
continue;
}
dfs(1, 0, 0);
if(flag == 1){
printf("yes\n");
} else{
printf("no\n");
}
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator