POJ1011Sticks(经典dfs)

作者：阿甘正传 | 来源：互联网 | 2014-08-26 14:19

Language:Default简体中文SticksTimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 120720 Accepted: 27951DescriptionGeorgetooks

Language:

Sticks

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 120720		Accepted: 27951

Description

George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.

Input

The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.

Output

The output should contains the smallest possible length of original sticks, one per line.

Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

Sample Output

6
5

Source

Central Europe 1995

题意：给你紧跟棍子，问可能是哪几根相同的棍子截成的，求可能的棍子的最小&＃20540;

很难的dfs，剪枝很重要，我也是看别人题解的⊙﹏⊙b汗，解释在代码中

#include
#include
#include
#include
#include
using namespace std;

#define N 105

int a[N],len,n;
int vis[N],sum;

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

bool dfs(int pos,int temp,int cut)
{
    if(cut==sum/len)  //拼凑成功
        return true;

    int i;

    for(i=pos;i

推荐阅读

case
GWT PopupPanel onKeyDownPreview 方法详解与实例

本文详细介绍了 GWT 中 PopupPanel 类的 onKeyDownPreview 方法，提供了多个代码示例及应用场景，帮助开发者更好地理解和使用该方法。 ... [详细]

蜡笔小新 2024-12-28 10:07:27
case
编写有趣的VBScript恶作剧脚本

本文将介绍如何编写一些有趣的VBScript脚本，这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例，帮助您了解VBScript的基本语法和功能。 ... [详细]

蜡笔小新 2024-12-28 09:46:23
case
Go语言基础：Hello World 实践

本文将介绍如何使用 Go 语言编写和运行一个简单的“Hello, World!”程序。内容涵盖开发环境配置、代码结构解析及执行步骤。 ... [详细]

蜡笔小新 2024-12-27 21:29:35
io
Installing the MongoDB PHP Driver on XAMPP for macOS

This guide provides a comprehensive step-by-step approach to successfully installing the MongoDB PHP driver on XAMPP for macOS, ensuring a smooth and efficient setup process. ... [详细]

蜡笔小新 2024-12-27 19:58:25
io
FastJSON解析与数据提取技巧

探讨如何高效使用FastJSON进行JSON数据解析，特别是从复杂嵌套结构中提取特定字段值的方法。 ... [详细]

蜡笔小新 2024-12-27 19:49:07
require
网络链路质量监控：Smokeping部署与配置

本文详细介绍了如何在Linux系统上安装和配置Smokeping，以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装，确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]

蜡笔小新 2024-12-27 19:31:05
require
使用动态规划算法求解0-1背包问题

本文介绍如何利用动态规划算法解决经典的0-1背包问题。通过具体实例和代码实现，详细解释了在给定容量的背包中选择若干物品以最大化总价值的过程。 ... [详细]

蜡笔小新 2024-12-27 19:17:15
io
解决VS2015类向导中'异常来自HRESULT:0x8CE0000B'错误的详细方法

本文介绍了在使用Visual Studio 2015进行项目开发时，遇到类向导弹出“异常来自 HRESULT:0x8CE0000B”错误的解决方案。通过具体步骤和实践经验，帮助开发者快速排查并解决问题。 ... [详细]

蜡笔小新 2024-12-27 19:01:41
range
词根词缀解析：greg、hap、helio及其他词源故事

本文基于刘洪波老师的《英文词根词缀精讲》，深入探讨了多个重要词根词缀的起源及其相关词汇，帮助读者更好地理解和记忆英语单词。 ... [详细]

蜡笔小新 2024-12-27 18:59:50
range
Python 的 10 个开发技巧！太实用了

1.如何在运行状态查看源代码？查看函数的源代码，我们通常会使用IDE来完成。比如在PyCharm中，你可以Ctrl+鼠标点击进入函数的源代码。那如果没有IDE呢？当我们想使用一个函 ... [详细]

蜡笔小新 2024-12-27 18:36:54
数组
数据管理权威指南：《DAMA-DMBOK2 数据管理知识体系》

本书提供了全面的数据管理职能、术语和最佳实践方法的标准行业解释，构建了数据管理的总体框架，为数据管理的发展奠定了坚实的理论基础。适合各类数据管理专业人士和相关领域的从业人员。 ... [详细]

蜡笔小新 2024-12-27 18:29:55
io
USACO 2014 Jan - Moolympics区间记录优化算法

题目描述：给定n个半开区间[a, b)，要求使用两个互不重叠的记录器，求最多可以记录多少个区间。解决方案采用贪心算法，通过排序和遍历实现最优解。 ... [详细]

蜡笔小新 2024-12-27 18:14:31
io
Dockerfile 编写与 Docker 网络配置详解

本文详细介绍了 Dockerfile 的编写方法及其在网络配置中的应用，涵盖基础指令、镜像构建与发布流程，并深入探讨了 Docker 的默认网络、容器互联及自定义网络的实现。 ... [详细]

蜡笔小新 2024-12-27 17:31:41
io
深入理解Java中的volatile、内存屏障与CPU指令

本文详细探讨了Java中volatile关键字的作用机制，以及其与内存屏障和CPU指令之间的关系。通过具体示例和专业解析，帮助读者更好地理解多线程编程中的同步问题。 ... [详细]

蜡笔小新 2024-12-27 17:26:33
io
如何在PHPcms网站中添加广告

本文详细介绍了在PHPcms网站后台添加广告的方法，涵盖多种常见的广告形式，如百度广告和Google广告，并提供了相关设置的步骤。同时，文章还探讨了优化网站流量的SEO策略。 ... [详细]

蜡笔小新 2024-12-27 17:13:07

阿甘正传

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章