xindoo is
always here

poj 2362 hdoj 1518 Square(搜索)


题目链接


大致题意:


给定一堆不定长度的小棒子,问他们能否构成一个正方形。


 


解题思路:


POJ1011的热身题,DFS+剪枝


 


本题大致做法就是对所有小棒子长度求和sum,sum就是正方形的周长,sum/4就是边长side。


问题就转变为:这堆小棒子能否刚好组合成为4根长度均为side的大棒子


 


不难了解,小棒子的长度越长,其灵活性越差。例如长度为5的一根棒子的组合方式要比5根长度为1的棒子的组合方式少,这就是灵活性的体现。


由此,我们首先要对这堆小棒子降序排序,从最长的棒子开始进行DFS


 


剪枝,有3处可剪:


1、  要组合为正方形,必须满足sum%4==0;


2、  所有小棒子中最长的一根,必须满足Max_length <= side,这是因为小棒子不能折断;


3、  当满足条件1、2时,只需要能组合3条边,就能确定这堆棒子可以组合为正方形。


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

bool vis[21];
int stick[21];
int n;
int side;

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

bool dfs(int num, int len, int s)//s为搜索起点
{
    if (num == 4)
        return true;
    for (int i = s; i < n; i++)
    {
        if (vis[i])
            continue;
        vis[i] = true;
        if (len+stick[i] < side)
        {
            if (dfs(num, len+stick[i], i))
            //这里解释游戏为什么有搜索起点这一变量,只有这用到了,如果len+stick[i] > side了
            //因为是非升序,len+stick[i-1] > side必然成立,从0开始就是浪费时间
                return true;
            /*开始这里我直接 return dfs(num, len+stick[i], i);貌似这样也可以,
            但的的确确是错的,直接返回会导致我们少判很多种情况*/
        }
        else if (len+stick[i] == side)
        {
            if (dfs(num+1, 0, 0))
                return true;
            //这里同上
        }
        vis[i] = false;
    }
    return  false;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &stick[i]);
            sum += stick[i];
        }
        side = sum/4;
        sort(stick, stick+n, cmp);
        if (sum % 4 || side < stick[0])
        //这里也可以去掉一些情况
        {
            puts("no");
            continue;
        }
        memset(vis, false, sizeof(vis));
        if (dfs(1, 0, 0))
            puts("yes");
        else
            puts("no");
    }
    return 0;
}


打赏
未经允许不得转载:XINDOO » poj 2362 hdoj 1518 Square(搜索)
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

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

支付宝扫一扫打赏

微信扫一扫打赏