专栏首页用户6093955的专栏Sticks(UVA - 307)【DFS+剪枝】

Sticks(UVA - 307)【DFS+剪枝】

Sticks(UVA - 307)

题目链接

算法

DFS+剪枝

1.这道题题意就是说原本有一些等长的木棍,后来把它们切割,切割成一个个最长为50单位长度的小木棍,现在想让你把它们组合成一个个等长的大木棍,要求这个拼接成的大木棍的长度最小。问最小长度是多少。(注意,在接下来的介绍中,将最后的大木棍表述为拼接木棍,小木棍还是叫小木棍)

2.看完这个题,基本思路是从一个小木棍开始找,找到一个未使用的小木棍后拼接,当拼接成的长度是所有小木棍长度和的约数时,就暂时把它定义为拼接木棍的最小长度,然后计算最后需拼接成多少个这个长度的拼接木棍,然后继续寻找,达到这个长度后累加,如果实在没有,重新定义拼接木棍的最下长度。

如果按部就班的按照上面的基本思路做肯定会超时的,而且涉及的点比较多,因为当你所找到的那个最小长度不能够让所有小木棍都能拼接成时,还需继续寻找,这样过于复杂。

那么换个思路,既然是拼接木棍,那么最终拼接木棍的最小长度一定大于等于所有小木棍的最大长度。

那么我们就可以从小木棍的最大长度这个地方开始枚举拼接木棍的长度,这是其中一个可以优化的地方。那什么时候到头呢,拼接木棍的长度最大可以枚举到所有小木棍的长度和,然后就不能再大了。考虑到拼接木棍的长度是小木棍长度和的约数,那么就可以枚举到长度和/2,因为大于长度和/2的部分就没有长度和的约数了(除了长度和本身),这样可以节省一定的时间。当满足条件时,直接退出循环,输出即可,如果循环了所有约数都不满足,直接输出长度和即可。

下面介绍几个剪枝的地方:

  • 将存储小木棍长度的数组从大到小排序,这样做的原因是长度大的小木棍相对于长度小的小木棍一定有相对较小的选择,这样在一定情况下节省了时间。
  • 枚举拼接木棍的长度时,只考虑约数(小木棍长度和的约数),其余的无需考虑。
  • 如果当前木棍与前一个木棍长度相同,并且前一个木棍拼接失败,那么直接跳过当前木棍即可。
  • 当目前拼接长度为0时,但尝试了所有的木棍都没有拼接成功,则证明这个拼接木棍的长度无法拼成,return false即可。

3.这道题是一道典型的DFS剪枝题目,涉及的剪枝比较多,稍有一点没涉及到就会TLE。

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1000;
int n, units[N];
int sum_length;     /*所有小木棍的总长度*/
bool st[N];         /*标记当前小木棍是否被使用*/
int res;            /*拼接长度*/
int cnt;            /*在拼接长度为res时最终能形成的拼接木棍的个数*/
bool dfs(int len, int k, int i) /*len表示当前的拼接长度,k表示满足res的拼接木棍的个数,i表示下标为i的这个木棍已经考虑完,再枚举时从下一个木棍开始枚举即可*/
{
    if(len == res)      
    {
        k++;            /*达到拼接长度时,累加拼接木棍的个数*/
        len = i = 0;
    }
    if(k == cnt) return true; 
    for(int j = i + 1; j < n; j++)
    {
        if(st[j]) continue;     /*当前木棍已经被使用,则不能再使用*/
        if(units[j] == units[j-1] && !st[j-1]) continue;    /*前一个木棍与它长度相同,但没被使用,那该木棍也无需再验证是否需要使用了*/
        if(units[j] + len > res) continue;                  /*大于拼接长度,则不能考虑*/
        st[j] = true;                                   
        if(dfs(len + units[j], k, j))
            return true;
        st[j] = false;
        if(len == 0)
            return false;
    }
    return false;
}
int main()
{
    while(cin >> n && n)
    {
        sum_length = 0;
        for(int i = 0; i < n; i++)
        {
            cin >> units[i];
            sum_length += units[i];
        }
        sort(units, units + n, greater<int>());

        for(res = units[0]; res <= sum_length / 2; res ++)
        {
            memset(st, 0, sizeof st);
            if(sum_length % res != 0) continue;
            cnt = sum_length / res;         /*预测的初始木棒个数*/
            st[0] = true;                   /*标记第一个最长的小木棍被使用*/
            if(dfs(units[0], 0, 0))
            {
                cout << res << endl;
                break;
            }
        }
        if(res > sum_length / 2)    /*大于它时,说明没有可形成的长度,直接输出长度和即可*/
            cout << sum_length << endl;
    }
}

思路来源

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Prime Path(POJ - 3126)【BFS+筛素数】

    1.题目主要就是给定你两个四位数的质数a,b,让你计算从a变到b共最小需要多少步。要求每次只能变1位,并且变1位后仍然为质数。

    _DIY
  • java 的任意进制间转换(很方便)

    参考自博客:https://www.cnblogs.com/TOM96/p/5240357.html

    _DIY
  • 【7-9 有重复的数据I (20 分)】【此题卡输入,需要自己写个输入挂】

    _DIY
  • 中国网络安全细分领域矩阵图(Matrix 2019.11)发布

    自 2018 年 11 月安全牛首次发布中国网络安全细分领域矩阵图 (Matrix 2018.11) 以来,矩阵图受到来自业内各方面的关注和认可。在以往成果的基...

    SDNLAB
  • 基于改进 LCS 的多机器人学习算法

    安川(中国)机器人有限公司是由日本国株式会社安川电机在中国投资的五家子公司之一。 ? ? ? ? ? ? ? ? ? ? ? ?

    机器人网
  • k8s的imagePullSecrets如何生成及使用

    公司的docker仓库(harbor),是私有的,需要用户认证之后,才能拉取镜像。

    py3study
  • 详解PHP 二维数组排序保持键名不变

    对二维数组指定的键名排序,首先大家想到的是array_multisort函数,关于array_multisort的用法我之前也写了一篇废话不多言,我们看个实例:

    砸漏
  • “死亡算法”:预测死亡时间准确率达90%!

    导读:在2017年11月的IEEE国际生物信息学与生物医学大会上,斯坦福大学计算机科学系的一名研究生Anand Avati对“死亡算法”的研究进行了报告:预测死...

    IT派
  • java之mybatis之动态sql

    2. choose, when, otherwise -----when可以有多个

    Vincent-yuan
  • docker 修改镜像和容器的存放路径 原

    此方法,启动Docker时发现存储目录依旧是/var/lib/docker,但是实际上是存储在数据盘的,你可以在数据盘上看到容量变化。

    拓荒者

扫码关注云+社区

领取腾讯云代金券