猿问

啊啊啊为什么没有人回答我的问题,快看看我,谢谢。。。

算法题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;
}

qq_我是谁_45
浏览 1293回答 0
0回答
随时随地看视频慕课网APP
我要回答