xindoo is
always here

poj 1011 hdoj 1455 Sticks(搜索+剪枝)


题目链接


大致题意:


有n跟棍, 求它们能组成最短且长度相同的棍的长度


 


解题思路:


DFS+剪枝


 


POJ2362的强化版,重点在于剪枝   建议你先看看这道题  here


 


令initlen为所求的最短原始棒长,maxlen为给定的棒子堆中最长的棒子,sumlen为这堆棒子的长度之和,那么initlen必定在范围[maxlen,sumlen]中,


cnt为可能组成的数目,也就是sunlen/maxlen。


 


根据棒子的灵活度(棒子越长,灵活度越低) DFS前先对所有棒子降序排序


 


剪枝:


1、  由于所有原始棒子等长,那么必有sumlen%Initlen==0,这个我在main函数中做了。


2、  若能在[maxlen,sumlen-InitLen]找到最短的InitLen,该InitLen必也是[maxlen,sumlen]的最短;若不能在[maxlen,sumlen-InitLen]找到最短的InitLen,则必有InitLen=sumlen;


3、  由于所有棒子已降序排序,在DFS时,若某根棒子不合适,则跳过其后面所有与它等长的棒子;


4、  最重要的剪枝:对于某个目标InitLen,在每次构建新的长度为InitLen的原始棒时,检查新棒的第一根stick[i],若在搜索完所有stick[]后都无法组合,则说明stick[i]无法在当前组合方式下组合,不用往下搜索(往下搜索会令stick[i]被舍弃),直接返回上一层


 代码

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

bool vis[65];
int stick[65];
int n, initlen, cnt;

bool cmp(int x, int y)
{
    return x > y;
}

bool dfs(int num, int len, int s)//s为搜索起点
{
    if (num == cnt)
        return true;
    int same = -1;
    for (int i = s; i < n; i++)
    {
        if (vis[i] || stick[i] == same)   //剪枝3
            continue;
        vis[i] = true;
        if (len+stick[i] < initlen)
        {
            if (dfs(num, len+stick[i], i))
                return true;
            else
                same = stick[i];
        }
        else if (len+stick[i] == initlen)
        {
            if (dfs(num+1, 0, 0))
                return true;
            else
                same = stick[i];
        }
        vis[i] = false;
        if (len == 0)       //剪枝4
            break;
    }
    return  false;
}

int main()
{
    while (scanf("%d", &n) && n)
    {
        int sumlen = 0;
        int maxlen = 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &stick[i]);
            sumlen += stick[i];
            if (stick[i] > maxlen)
                maxlen = stick[i];
        }
        sort(stick, stick+n, cmp);
        for (initlen = maxlen; initlen <= sumlen; initlen++)// 剪枝1
        {
            if (sumlen%initlen)  //剪枝2
                continue;
            cnt = sumlen/initlen;
            memset(vis, false, sizeof(vis));
            if (dfs(1, 0, 0))
            {
                printf("%d\n", initlen);
                break;
            }
        }
    }
    return 0;
}

打赏
未经允许不得转载:XINDOO » poj 1011 hdoj 1455 Sticks(搜索+剪枝)
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏