解题报告 『小木棍[数据加强版](深度优先搜索 + 剪枝)』_weixin_30662109的博客-程序员宝宝

技术标签: 数据结构与算法  

原题地址

本以为是一道水题,但死活只能拿到27分,总之详情见代码。

本题我用了4类剪枝,剪枝(1,2)没什么好说的,这里说一下剪枝(3,4):

剪枝(3):如果当前原始木棒中“尝试拼入的第一根木棒”的递归分支就返回失败,那么直接判定当前分支失败;

剪枝(4):如果在当前原始木棒中拼入一根木棒后,木棒恰好被拼接完整,并且“接下来拼接剩余木棒”的递归分支返回失败,那么直接判定当前分支失败。

以上两个剪枝分别利用了“空木棒的等效性”和“贪心”。

 

代码实现如下:

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (register int i = (a); i <= (b); i++)

const int maxn = 1e2;

int n, cnt, len, tot;
int a[maxn];
bool vis[maxn];

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

void origin() {memset(vis, 0, sizeof(vis));}

int read() {
    int x = 0, flag = 0;
    char ch = ' ';
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') {
        flag = 1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    return flag ? -x : x;
}

int dfs(int stick, int cab, int last) {
    if (stick > cnt) return 1;
    if (cab == len) return dfs(stick + 1, 0, 1);
    int fail = 0;//剪枝(2),不解释.
    rep(i, last, n) {
        if (!vis[i] && cab + a[i] <= len && a[i] != fail) {
            vis[i] = 1;
            if (dfs(stick, cab + a[i], i + 1)) return 1;
            fail = a[i];
            vis[i] = 0;
            if (!cab || cab + a[i] == len) return 0;//剪枝(3,4).
        }
    }
    return 0;
}

void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int main() {
    int sum = 0, val = 0;
    n = read();
    rep(i, 1, n) {
        int u = read();
        if (u > 50) continue;
        else {
            a[++tot] = u;
            sum += u;
            val = max(u, val);
        }
    }
    sort(a + 1, a + n + 1, cmp);//剪枝(1),不解释.
    //一开始用的宏定义rep,WA的只有27分.
    for (len = val; len <= sum; len++) {
        if (sum % len) continue;
        cnt = sum / len;
        origin();
        if (dfs(1, 0, 1)) {
            write(len);
               break;
        }
    }
    return 0;
}
View Code

转载于:https://www.cnblogs.com/Kirisame-Marisa/p/10805543.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30662109/article/details/95859954

智能推荐

ANT手册篇_sxyandapp的博客-程序员宝宝_ant手册

毫无疑问,ant在文件操作、命令执行、服务器操作等方面相比maven有绝对的优势。本文特此整理了ant一些常用命令,方便日后查阅和使用。加载属性(property)注意:xml中定义的属性,先定义的不会被后面的覆盖。属性文件中定义的属性,后者会覆盖前者。 定义一个属性<property name="akey" value="avalue" /> 加载属性文件<property file=

[CUDA]关于centos如何安装cuda driver_浮世绘荒年的博客-程序员宝宝

yum -y updateyum -y groupinstall “GNOME Desktop” “Development Tools”yum -y install kernel-develEdit /etc/default/grub. Add “rd.driver.blacklist=nouveau nouveau.modeset=0″ to “GRUB_CMDLINE_LINUX”grub2-

html判断是否为文件夹,FSO(fileSystemObject)判断文件及文件夹是否存在_weixin_39665762的博客-程序员宝宝

fso中判断文件夹是否存在set fso = server.createobject("scripting.filesystemobject")if fso.FolderExists(server.mappath("../folderName"))=falsethenREsponse.write("此文件夹不存在")end iffso中判断文件是否存在set fso = server.create...

JavaScript基础(八)---arguments参数列表_是火锅吖的博客-程序员宝宝_js参数列表

arguments参数列表function fn(){ console.log(arguments);//这个关键词只能出现在函数中,参数列表 console.log(arguments[0],arguments[1],arguments[2],arguments[3]); // 分别对应传入参数 } fn(1,2,3,4);1.这个关键词只能出现在函数中,当前参数列表(实参)2.不确定到底传入多

js实现指定dom元素滚动到可视窗口_start_sea的博客-程序员宝宝_js将元素滚动到可视范围

js实现指定dom元素滚动到可视窗口const rollDom = document.getElementById('domId')  // 获取想要滚动的dom元素rollDom.scrollIntoView({ block: 'center' })  // 通过scrollIntoView方法滚动到可视窗口中间block的值:start、center、end、nearest如果对你有帮助,记得点赞噢(~~)...

CABasicAnimation, CAKeyframeAnimation,CAAnimationGroup动画的用法_夕阳下的守望者的博客-程序员宝宝

一.CAAnimation动画CABasicAnimation, CAKeyframeAnimation 可以通过 animationWithKeyPath 来初始化  CABasicAnimation 有  fromValue 和  toValue 这两个属性CAKeyframeAnimation 有 path(路径)这个属性iOS9新出了一个动画CASpringAnim

随便推点

在Java中 什么叫包-包有什么用途-如何创建包-_凰宸的博客-程序员宝宝_什么是包

1.什么叫包? 为了更好地组织类,Java提供了包机制。包是类的容器,用于分隔类名空间。如果没有指定包名,所有的示例都属于一个默认的无名包。Java中的包一般均包含相关的类,例如,所有关于交通工具的类都可以放到名为Transportation的包中。 2.包有什么用途? 如上所述,更好的组织类,防止在一个空间下出现类重名啊这些情况;表明类之间的层次关系。 3.如何创建包? 不使用IDE工具

一次耐人寻味的SQL优化:除了SQL改写,还要考虑什么?_weixin_34032827的博客-程序员宝宝

黄浩2016-11-03 10:36:26作者介绍黄浩,现任职于中国惠普,从业十年,始终专注于SQL。在华为做项目的两年多,做过大大小小的SQL多达1500个。闲暇之余,喜欢将部分案例写成博客发表在华为内部数据库官方社区,反响强烈,已连续四个月蝉联该社区最佳博主。目前已开设专栏“优哉悠斋”,成为首个受邀社区“专家访谈”的外协人员。...

常见的DDL,DML,DCL_Echo_ac的博客-程序员宝宝

SQL: 指结构化查询语言,全称是 Structured Query Language。DDL:Data Definition Language,数据定义语言(create ,alter drop)DML:Data Manipulation Language,数据操作语言,(select, delete,update,insert)DCL:Data Control Language, 数据控制语言,(grant,revoke,commit, rollback)...

oracle数据库安装后如何建立自己的数据库_sunyllove的博客-程序员宝宝_安装完oracle后怎么创建数据库

oracle数据库安装后如何建立自己的数据库 (2012-05-27 15:49:50)转载▼标签: 数据库 oracle 创建表 杂谈       最近,有个人找自己做oracle方面的东西,自己之前搞过数据库,但是没有搞过oracle数据库,有点担心,但是,之后研究了一下

Android开发中java.lang.RuntimeException: Unable to start activity ComponentInfo问题_嗯哼丶苏苏的博客-程序员宝宝

今天学着写了个底部导航栏滑动切换页面,主要是使用Fragment+ViewPager,项目可编译,但是运行就会报错停止,错误提示如下:手机程序中则是:通过查看错误信息发现报错是MainActivity中的 setContentView(R.layout.activity_main); 但是MainActivity并没有报错,查看R.layout.activity_main布局文件也...