DFS題，優(yōu)化比較麻煩。首先要把棍子從大大小排序下，因為大棍子拼不成的概率大于小棍子拼不成的概率。主要有兩個優(yōu)化：
1.當(dāng)當(dāng)前棍子是某一跟整個棍子的開始時，如果搜不到結(jié)果，那么就不要再搜了。因為：開頭的棍子限制最小，并且它總要作為某一根整個棍子的一部分。
2.當(dāng)當(dāng)前棍子和前面的棍子長度相等，并且前面那根沒用過。直接跳過。（這個優(yōu)化主要是對坑爹數(shù)據(jù)進(jìn)行的，主要還是第一個優(yōu)化。）。
別的優(yōu)化基本都是浮云。歡迎噴子，歡迎指點。
#include <cstdio>
#include <cstdlib>
#include <cstring>
int stick[110];
int flag[110];
int scount;
int find;
int cmp(const void* a,const void* b)
{
return *(int*)b - *(int*)a;
}
int testdata = 0;
void dfs(int start,int len,int N,int count)
{
testdata++;
int i,j;
if( (len == 0 && count == 0) || find == 1)
{
find = 1;
return;
}
if(len == 0)
{
i =0;
while(flag[i] == 1)
i++;
flag[i] = 1;
if(stick[i] != N)
dfs(i+1,stick[i],N,count);
else
dfs(0,0,N,count-1);
flag[i] = 0;
return;
}
for(i=start;i<scount;i++)
{
if(i && !flag[i-1] && !flag[i] && stick[i] == stick[i-1])
continue;
if(!flag[i])
{
if(len+stick[i] < N)
{
flag[i] = 1;
dfs(i+1,len+stick[i],N,count);
flag[i] = 0;
}
else if(len+stick[i] == N)
{
flag[i] = 1;
dfs(0,0,N,count-1);
flag[i] = 0;
break;
}
}
}
}
int main()
{
int i;
int total;
while(scanf("%d",&scount)!=EOF && scount)
{
int minstart = 0;
total = 0;
for(i=0;i<scount;i++)
{
scanf("%d",&stick[i]);
total += stick[i];
}
qsort(stick,scount,sizeof(int),cmp);
minstart = stick[0];
find = 0;
for(i=minstart;;i++)
{
if(total%i == 0)
{
memset(flag,0,sizeof(flag));
dfs(0,0,i,total/i);
//printf("dfs(0.0.%d.%d)\n",i,total/i);
//printf("total::%d\n",total);
//printf("testdata::%d\n",testdata);
//printf("%d\n",i);
if(find == 1)
{
printf("%d\n",i);
break;
}
}
}
}
return 0;
}