这个题目是北大上面深度优先遍历的经典算法,主要的减枝策略是对数组进行排序,在每次搜索时一定要把第一个放进去。地址:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1011
#include <stdio.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <stdlib.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int stick[64];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int used[64];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n, m, len;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void init ( int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( int i=1; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
used[i] = 0;
}
used[0] = 1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int cmp ( const void *a, const void *b )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return *( int * )b - *( int * )a;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int dfs ( int start, int no, int cur, int last )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i, j;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( ! last )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( cur == len )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return 1;
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( cur == len )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( m - no > last )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( i=1; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( ! used[i] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
break;
}
}
used[i] = 1;
if ( dfs ( i+1, no+1, stick[i], last-1 ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return 1;
}
used[i] = 0;
return 0;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( m - no > last - 1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return 0;
}
for ( i=start; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( ! used[i] && cur+stick[i] <= len )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
used[i] = 1;
if ( dfs ( i+1, no, cur+stick[i], last-1 ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return 1;
}
used[i] = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( j=i+1; j<n; j++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( stick[i] != stick[j] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
break;
}
}
i = j - 1;
}
}
return 0;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int max, sum;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while ( scanf ( "%d", &n ) != EOF && n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
sum = 0;
max = -1;
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf ( "%d", &stick[i] );
sum += stick[i];
if ( stick[i] > max )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
max = stick[i];
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
qsort ( stick, n, sizeof ( int ), cmp );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
m = n + 1;
init (n);
while ( -- m )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( ( ! ( sum % m ) ) && ( ( sum / m ) >= max ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
len = sum / m;
if ( dfs ( 1, 1, stick[0], n-1 ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
break;
}
}
}
printf ( "%d\n", len );
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)