文档章节

P1120 小木棍 数据加强版

机智的帝江
 机智的帝江
发布于 2016/10/30 09:59
字数 462
阅读 18
收藏 0

题目描述

乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过50。

现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。

给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。

输入输出格式

输入格式:
输入文件共有二行。

第一行为一个单独的整数N表示砍过以后的小木棍的总数,其中N≤65

(管理员注:要把超过50的长度自觉过滤掉,坑了很多人了!)

第二行为N个用空个隔开的正整数,表示N根小木棍的长度。

输出格式:
输出文件仅一行,表示要求的原始木棍的最小可能长度

输入输出样例

输入样例
9
5 2 1 5 2 1 5 2 1
输出样例
6

这题。。。没啥难度。。就是搜的时候注意下题目给的那个坑。。可能有初始大于50的棍子。。

#include<algorithm>
#include<cstdio>
//#define fo(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int n,sum,len,tot,ans;
int a[101];
bool vis[101];
bool cmp(int x,int y) {return x>y;}
bool dfs(int now,int next,int d)
{
    if(d==tot) 
    {ans=len;return 1;}
    if(now==0) {if(dfs(len,1,d+1)) return 1;}
    for(int i=next;i<=n;i++)
      if(!vis[i] && a[i]<=now)
      {
          vis[i]=1;
          if(dfs(now-a[i],i+1,d)) return 1;
          vis[i]=0;
          if(now==a[i] || now==len) break;  
          while(a[i+1]==a[i]) i++;  
      }
    return 0;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]>50) n--,i--;
        else sum+=a[i];
    }
    sort(a+1,a+n+1,cmp);  
    for(len=a[1];len<=sum;len++) 
      if(sum%len==0)
      {
        tot=sum/len;
        if(dfs(len,1,0)) break;
      }
    printf("%d\n",ans);
    return 0;
}

本文转载自:http://blog.csdn.net/loi__dijiang/article/details/52774176

机智的帝江
粉丝 0
博文 89
码字总数 4734
作品 0
莱芜
程序员
私信 提问
题解 P1120 【小木棍 [数据加强版]】

题面 乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过50。 现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。 给出每段小...

Chicago_01
2018/11/07
0
0
POJ 1948 Triangular Pastures 【经典问题 - 二维01背包求最大三角形】

传送门 // 题意 : 现在有n根木棍, 要求把这些木棍全部用上, 能组成的最大三角形面积是多少. 不能组成输出-1. 思路: 这个问题就很经典了, 我们首先看数据范围, 最多40根, 每根最长40, 那么周...

anxdada
2018/03/19
0
0
寻找“最好”(5)——无解之解

  我所在的城市里,市中心有一座邮政大楼,小时候,那可是全市最高建筑!每到整点,楼顶的大钟就奏起《松花江上》,即使相隔很远也能听见。当时我对大楼的高度充满好奇,经常想着怎样用格尺...

我是8位的
2018/08/27
0
0
记一道面试题

题目:有n个台阶,每次可以走的步数任意,问有多少种走法? 面试时由于太紧张没答上,回来后仔细想了想,顺便记一下。 我的思路是n个台阶,相当于是有n个小球依次排开,有n-1个木棍,将0~n-1...

纳兰清风
2015/10/03
194
0
Wooden Sticks(POJ1065)(贪心)

木棍 描述 有一堆木棍。每根杆的长度和重量是预先已知的。这些木棍将由木工机器逐一加工。它需要一些时间,称为设置时间,以便机器准备处理棒。设置时间与清洁操作以及更换机器中的工具和形状...

回忆酿的甜
06/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

64.监控平台介绍 安装zabbix 忘记admin密码

19.1 Linux监控平台介绍 19.2 zabbix监控介绍 19.3/19.4/19.6 安装zabbix 19.5 忘记Admin密码如何做 19.1 Linux监控平台介绍: 常见开源监控软件 ~1.cacti、nagios、zabbix、smokeping、ope...

oschina130111
今天
10
0
当餐饮遇上大数据,嗯真香!

之前去开了一场会,主题是「餐饮领袖新零售峰会」。认真听完了餐饮前辈和新秀们的分享,觉得获益匪浅,把脑子里的核心纪要整理了一下,今天和大家做一个简单的分享,欢迎感兴趣的小伙伴一起交...

数澜科技
今天
7
0
DNS-over-HTTPS 的下一代是 DNS ON BLOCKCHAIN

本文作者:PETER LAI ,是 Diode 的区块链工程师。在进入软件开发领域之前,他主要是在做工商管理相关工作。Peter Lai 也是一位活跃的开源贡献者。目前,他正在与 Diode 团队一起开发基于区块...

红薯
今天
6
0
CC攻击带来的危害我们该如何防御?

随着网络的发展带给我们很多的便利,但是同时也带给我们一些网站安全问题,网络攻击就是常见的网站安全问题。其中作为站长最常见的就是CC攻击,CC攻击是网络攻击方式的一种,是一种比较常见的...

云漫网络Ruan
今天
11
0
实验分析性专业硕士提纲撰写要点

为什么您需要研究论文的提纲? 首先当您进行研究时,您需要聚集许多信息和想法,研究论文提纲可以较好地组织你的想法, 了解您研究资料的流畅度和程度。确保你写作时不会错过任何重要资料以此...

论文辅导员
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部