为了账号安全,请及时绑定邮箱和手机立即绑定

算法题sticks交上去总是答案错误50%是什么原因?

算法题sticks交上去总是答案错误50%是什么原因?

qq_我是谁_45 2018-06-10 11:40:40
基本思想使剪枝和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;}
查看完整描述

目前暂无任何回答

  • 0 回答
  • 0 关注
  • 1379 浏览
慕课专栏
更多

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信