算法题sticks交上去总是答案错误50%是什么原因?
基本思想是dfs和剪枝
我的代码:
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int visit[70] = { 0 }, sticks[70];
int sum=0,n=0,len;
bool compare(int a, int b)
{
return a>b;
}
int main()
{
bool dfs(int start,int snowlen,int nowlen);
while (cin >> n)
{
if (n == 0)
break;
for (int i = 0; i < n; i++)
{
cin >> sticks[i];
sum += sticks[i];
}
sort(sticks, sticks + n, compare);
for (len = sticks[0]; len <= sum; len++)
{
if (sum%len == 0)
{
if (dfs(0, 0, 0))
{
cout << len << endl;
break;
}
}
memset(visit, 0, sizeof(visit));
}
memset(sticks, 0, sizeof(sticks));
sum = 0;
}
return 0;
}
bool dfs(int start,int snowlen, int nslen)
{
for (int i = start; i < n; i++)
{
if (snowlen + sticks[i] <= len && visit[i] == 0)
{
visit[i] = 1;
int x,ss;
x = i;
ss = snowlen + sticks[i];
nslen += sticks[i];
if (snowlen + sticks[i] == len)
{
x = 0;
ss = 0;
}
if (nslen == sum)
return true;
if (dfs(x, ss, nslen) == true)
{
return true;
}
visit[i] = 0;
if (snowlen + sticks[i] == len || snowlen == 0)
return false;
while (sticks[i + 1] == sticks[i])
++i;
}
}
return false;
}
相关分类