DFS搜索,是stick的简化版本
#include <stdio.h>

#include <stdlib.h>

int stick[64];

int used[64];

int n, m, len;

void init ( int n )
  {

for ( int i=1; i<n; i++ )
 {
used[i] = 0;
}
used[0] = 1;
}

int cmp ( const void *a, const void *b )
  {

return *( int * )b - *( int * )a;
}

int dfs ( int start, int no, int cur, int last )
  {

int i, j;

if ( ! last )
 {
if ( cur == len )
 {
return 1;
}
return 0;
}

if ( cur == len )
 {
if ( m - no > last )
 {
return 0;
}

for ( i=1; i<n; i++ )
 {
if ( ! used[i] )
 {
break;
}
}
used[i] = 1;
if ( dfs ( i+1, no+1, stick[i], last-1 ) )
 {
return 1;
}
used[i] = 0;
return 0;
}
else
 {
if ( m - no > last - 1 )
 {
return 0;
}
for ( i=start; i<n; i++ )
 {
if ( ! used[i] && cur+stick[i] <= len )
 {
used[i] = 1;
if ( dfs ( i+1, no, cur+stick[i], last-1 ) )
 {
return 1;
}
used[i] = 0;

for ( j=i+1; j<n; j++ )
 {
if ( stick[i] != stick[j] )
 {
break;
}
}
i = j - 1;
}
}
return 0;
}
}

int main ()
  {

int t, max, sum;

while ( scanf ( "%d", &t ) != EOF )
 {
while ( t -- )
 {
scanf ( "%d", &n );
sum = 0;
max = -1;
for ( int i=0; i<n; i++ )
 {
scanf ( "%d", &stick[i] );
sum += stick[i];
if ( max < stick[i] )
 {
max = stick[i];
}
}

m = 4;
if ( sum % m )
 {
printf ( "no\n" );
}
else
 {
if ( sum / m < max )
 {
printf ( "no\n" );
}
else
 {
init ( n );
len = sum / m;
if ( dfs ( 1, 1, stick[0], n-1 ) )
 {
printf ( "yes\n" );
}
else
 {
printf ( "no\n" );
}
}
}
}
}
return 0;
}

|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
29 | 30 | 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 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论

阅读排行榜
评论排行榜
|
|