2 qq3434569 qq3434569 于 2017.08.04 13:42 提问

POJ 1011 Sticks (dfs) 我照着题解敲的,哪位大佬看看为什么WA了

[code=c]#include
#include
#include
#include
using namespace std;
int v[70];
int a[70];
int n;
int ans;

int dfs(int index, int sum)//下标和当前木棒长度的总和
{
sum += a[index];
int l=sum;
if (sum == ans)return l;//找到就返回
if (sum > ans)return l;//大了就说明选择的这根木棒不对 返回
for (int i = index + 1; i < n; i++)//将所以可以选择的木棒枚举一遍
{
if (v[i] == 0)
{
v[i] = 1;

        l=dfs(i, sum);
        if (l>ans)//大了就找下一个
        {
            v[i] = 0;
            while (1)//去除与这个长度相等的木棒  因为肯定也不满足
            {
                if (a[i + 1] != a[i])break;
                i++;
            }
        }
        else if (l < ans) {  return l; }//如果长度不够 就直接结束dfs 因为后面的木棒长度更小 永远也得不到结果
        else return l;//找到了 就退出dfs
    }
}
return l;   //枚举完了长度还不够 退出dfs

}

bool cmp(int a, int b)
{
return a > b;
}

int main()
{
while (cin >> n)
{
if (n == 0)break;

    int k=0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        k+=a[i];            //所有的和 作为结束的条件
    }
    sort(a, a + n, cmp);//从大到小排序

    for (ans = a[0];ans<k; ans++)//结果一定不小于最长的木棒
    {
        bool flag = true;//判断是否找到循环退出的条件
        memset(v, 0, sizeof(v));//每次没找到都要置零
        for (int j = 0; j < n; j++)//把每个木棒遍历一遍是否能找到答案
        {
            if (v[j] == 0)
            {
                v[j] = 1;
                if (dfs(j, 0) != ans) { flag = false; break; }//如果不对就退出这个循环 看下一个结果是否正常
            }
        }
        if (flag == true)break;
    }
    cout << ans << endl;
}
return 0;

}[/code]

1个回答

shen_wei
shen_wei   Ds   Rxr 2017.08.04 14:21
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!