| Sticks |
【 随 笔 】：很久之前就遇到这道题，题目意思容易理解，后来自己想到了一个法子，思路也很清晰就将代码敲出来了，用了位运算（后来问师兄是说状态压缩，其实我不知道什么是状态压缩~_~），不过提交的时候超时了，我想着优化代码，尽可能加剪枝的条件，却无从下手，后来搜题解搜到了师兄的博客，题解中剪枝的条件自己能想到的五个中了三个，剩下两个剪枝也容易理解，整个DFS的思路也容易理解，这点值得反思，其中的原因我想是自己先入为主了，在之前的思路上瞎折腾，未果却也不接受考虑另外的可能，其实看了师兄的代码思路后，也就是普普通通的暴力回溯，不多说，先保存TL的代码：
【AC的代码链接】：http://www.cppblog.com/y346491470/articles/155318.html
【超时的代码】
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#define MAXN 500
using namespace std;
int sticks[MAXN];
bool visit[MAXN];
int n, sumlen, res; bool judge(int fac)
{
int i;
for(i=; i<n && visit[i]; ++i);
if(i<n) return false;
else
{
res = fac;
return true;
}
} bool Traverse(int fac)
{
for(int i=; i<(<<n); ++i)
{
int subsum = ;
bool is_useful = true;
for(int k=; k<n; ++k)
{
if(i&(<<k))
{
if(visit[k] || subsum > fac)
{
is_useful = false;
break;
}
else subsum += sticks[k];
}
}
if(is_useful && subsum == fac)
{
for(int k=; k<n; ++k)
{
if(i&(<<k)) visit[k] = true;
}
if(judge(fac) || Traverse(fac)) return true;
for(int k=; k<n; ++k)
{
if(i&(<<k)) visit[k] = false;
}
}
}
return false;
} int main()
{
#ifndef ONLINE_JUDGE
freopen("F:\\test\\input.txt", "r", stdin);
#endif // ONLINE_JUDGE
while(cin>>n, n)
{
int curmax = ;
sumlen = ;
for(int i=; i<n; ++i)
{
cin>>sticks[i];
curmax = curmax > sticks[i] ? curmax :sticks[i];
sumlen += sticks[i];
}
for(int fac = curmax; fac <= sumlen; ++fac)
{
if(sumlen%fac == )
{
memset(visit, false, sizeof(visit));
if(Traverse(fac))
{
cout<<res<<endl;
break;
}
}
}
} return ;
}
自己后来又重新写了一遍，写的过程中感觉还是对回溯的理解还是不够深，回溯本是暴力的一种，所以这题也能看到一层一层搜索的路径，没有太多的技巧，都是根据题目的特性找规律，充分利用从而写出剪枝的条件，避免了超时，效率也更高。
【AC代码】
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#define MAXN 1000 using namespace std; int sticks[MAXN];
bool visit[MAXN];
int n, length, sum, sumlen; bool cmp(const int& a, const int& b)
{
return a>b;
} bool Traverse(int num, int len, int cur)
{
if(num == sum) return true;
for(int i=cur; i<n; ++i)
{
if(!visit[i] && !(i && !visit[i-] && sticks[i] == sticks[i-]))
{
if(len+sticks[i] == length)
{
visit[i] = true;
if(Traverse(num+, , )) return true;
visit[i] = false;
return false;
}
else if(len+sticks[i] < length)
{
visit[i] = true;
if(Traverse(num, len+sticks[i], i+)) return true;
visit[i] = false;
if(len == ) return false;
}
}
}
return false;
} int main()
{
#ifndef ONLINE_JUDGE
freopen("F:\\test\\input.txt", "r", stdin);
#endif // ONLINE_JUDGE
while(cin>>n, n)
{
int curmax = ;
sumlen = ;
for(int i=; i<n; ++i)
{
cin>>sticks[i];
sumlen += sticks[i];
}
sort(sticks, sticks+n, cmp);
for(int fac = sticks[]; fac <= sumlen; ++fac)
{
if(sumlen%fac == )
{
length = fac;
sum = sumlen/fac;
memset(visit, false, sizeof(visit));
if(Traverse(,,)) break;
}
}
cout<<length<<endl;
} return ;
}