Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 110416 | Accepted: 25331 |
Description
Input
Output
Sample Input
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
Sample Output
6
5
一个dfs题,讲解我就copy点大神的了
经典搜索题,黑书上的剪枝例题。剪枝的空间很大,剪枝前写下朴素的搜索框架(黑字部分),枚举原始木棍的长度及由那些小木棍组合。原始木棍长度一定是小木棍总长度的约数,因此可以减少枚举量。
越长的木棍对后面木棍的约束力越大,因此要把小木棍排序,按木棍长度从大到小搜索,这样就能在尽可能靠近根的地方剪枝。(剪枝一)
如果当前木棍能恰好填满一根原始木棍,但因剩余的木棍无法组合出合法解而返回,那么让我们考虑接下来的两种策略,一是用更长的木棍来代替当前木棍,显然这样总长度会超过原始木棍的长度,违法。二是用更短的木棍组合来代替这根木棍,他们的总长恰好是当前木棍的长度,但是由于这些替代木棍在后面的搜索中无法得到合法解,当前木棍也不可能替代这些木棍组合出合法解。因为当前木棍的做的事这些替代木棍也能做到。所以,当出现加上某根木棍恰好能填满一根原始木棍,但由在后面的搜索中失败了,就不必考虑其他木棍了,直接退出当前的枚举。(剪枝二)
显然最后一根木棍是不必搜索的,因为原始木棍长度是总木棍长度的约数。(算不上剪枝)
考虑每根原始木棍的第一根木棍,如果当前枚举的木棍长度无法得出合法解,就不必考虑下一根木棍了,当前木棍一定是作为某根原始木棍的第一根木棍的,现在不行,以后也不可能得出合法解。也就是说每根原始木棍的第一根小木棍一定要成功,否则就返回。(剪枝四)
剩下一个通用的剪枝就是跳过重复长度的木棍,当前木棍跟它后面木棍的无法得出合法解,后面跟它一样长度的木棍也不可能得到合法解,因为后面相同长度木棍能做到的,前面这根木棍也能做到。(剪枝五)
这题主要就是剪枝,看了别人的代码看了好久才写的
#include<iostream>
#include<algorithm>
using namespace std; int a[70],visit[70],len,n; bool cmp(const int a,const int b)
{
return a>b;
} bool dfs(int f,int i,int sum)
{
int j;
if(i==0)
{
if(sum==len)
return true;//全部的都已经找完了,都匹配
i=len;
for(j=0;visit[j];j++)
;
visit[j]=1;
if(dfs(j+1,i-a[j],sum-len))//此处j+1是因为j已经搜过了
{
return true;
}
visit[j]=0;//失败了
}
else
{
for(j=f;j<n;j++)
{
if(visit[j])
continue;
if(j>0&&a[j]==a[j-1]&&!visit[j-1])
{
continue;
}
visit[j]=1;
if(a[j]<=i&&dfs(j+1,i-a[j],sum))//这里j+1和上面意思一样,原来看别人的写的是j,让我纠结了好久,加不加1只是对结果没影响
return true;
visit[j]=0;
if(a[j]==i)//刚好把木棒填满,并且搜索失败,这种情况不可能了,无论如何满足不了题意的
break;
}
}
return false;
}
int main()
{
int i,j,sum;
while(scanf("%d",&n)!=EOF&&n)
{
for(i=0;i<n;i++)
visit[i]=0;
sum=0;
for(i=0;i<n;i++)
{
scanf("%d",a+i);
sum+=a[i];
}
sort(a,a+n,cmp);
j=sum/2;
for(i=a[0];i<=j;i++)
{
len=i;
if(sum%i==0)
{
if(dfs(0,i,sum))//序号,还差的长度(不包括当前棒),总木棒剩余的长度
break;//这个dfs有点特殊,dfs里面的意思不太一样,它没有标记0,这是为了方便写
}
}
if(i>j)
printf("%d\n",sum);
else printf("%d\n",i);
}
return 0;
}
/*
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
*/