POJ 2362 - Square


问题描述

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

解题思路

[POJ1011](./4` 就是边长side 。

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

不难理解,小棒子的长度越长,其灵活性越差。

例如长度为5的一根棒子的组合方式要比5根长度为1的棒子的组合方式少,这就是灵活性的体现。

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

剪枝,有3处可剪:

  • 要组合为正方形,必须满足 sum%4==0
  • 所有小棒子中最长的一根,必须满足 Max_length <= side,这是因为小棒子不能折断;
  • 当满足前两个条件时,只需要能组合3条边,就能确定这堆棒子可以组合为正方形。

AC 源码

//Memory Time 
//244K   79MS 

#include<iostream>
#include<algorithm>
using namespace std;

int cmp(const void* a,const void* b)  //降序
{
    return *(int*)b-*(int*)a;
}

int n;  //木棒数量
int side;  //正方形边长
bool dfs(int* stick,bool* vist,int num,int len,int s)  //num:已组合的正方形的边数  len:当前组合的边已组合的长度,len<=side
{                                                      //s:stick[]的搜索起点
    if(num==3)   //剪枝3,当满足剪枝1和2的要求时,只需组合3条side,剩下的棒子必然能够组成最后一条side
        return true;

    for(int i=s;i<n;i++)
    {
        if(vist[i])
            continue;

        vist[i]=true;
        if(len+stick[i]<side)
        {
            if(dfs(stick,vist,num,len+stick[i],i))  //继续构建当前side
                return true;
        }
        else if(len+stick[i]==side)
        {
            if(dfs(stick,vist,num+1,0,0))  //构建新side
                return true;
        }
        vist[i]=false;
    }

    return false;
}

int main(void)
{
    int time;
    cin>>time;
    for(int t=0;t<time;t++)
    {    
        int sum=0;  //所有木棒长度之和

        cin>>n;
        int* stick=new int[n];
        bool* vist=new bool[n];

        for(int i=0;i<n;i++)
        {
            cin>>stick[i];
            vist[i]=false;

            sum+=stick[i];
        }        

        if(n<4 || sum%4!=0)    //剪枝1,不能构成正方形
        {
            cout<<"no"<<endl;
            continue;
        }

        qsort(stick,n,sizeof(int),cmp);   //降序排列,先组合长棒,因为长棒相对于短棒的组合灵活性较低

        side=sum/4;  //边长
        if(side<stick[0])   //剪枝2,side<max_stick
        {
            cout<<"no"<<endl;
            continue;
        }

        if(dfs(stick,vist,0,0,0))
            cout<<"yes"<<endl;
        else
            cout<<"no"<<endl;

        delete stick;
        delete vist;
    }
    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
 上一篇
ACM 测试数据合集 ACM 测试数据合集
注:本文部分链接可能已失效,测试数据仅供参考调试之用,希望各位同学不要用来刷题 地区赛http://icpc.baylor.edu/past/icpc2003/regionals/report.html USACO 2006年Novem
2011-08-16
下一篇 
POJ 3274 - Gold Balanced Lineup POJ 3274 - Gold Balanced Lineup
POJ 3274 - Gold Balanced Lineup Time: 2000MS Memory: 65536K 难度: 初级 分类: 高效查找法 问题描述农夫约翰的N(1≤N≤100000)头奶牛有很多相同之处。其实,约翰己经将
2011-08-11
  目录