poj 1011 Sticks (DFS+剪枝)

poj 1011 Sticks (DFS+剪枝)

大家好,又见面了,我是全栈君。

Sticks
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 127771   Accepted: 29926

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

题目链接:http://poj.org/problem?id=1011


题目大意:有n根木棍。用它们拼成一些等长的木棍,求拼出的木棍的最短长度。


解题思路:这题的时间限制特别严格。

DFS+剪枝,剪枝较多。首先由多到少枚举木棍数目num。即从n到1,要满足木棍总长度是num的倍数,且拼出的长度要不小于最长的木棍长度,否则无法拼,搜索到答案后退出循环,保证求出的木棍长最短。

剪枝:1.木棍由长到短排序。

   2.訪问过的木棍或者加上当前木棍长度后超过了目标长度,则跳过本次循环。

   3.若当前木棍和上一根木棍长度同样而且上一根木棍没用到,则跳过本次循环。

   4.dfs中标记開始木棍下标。


代码例如以下:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[66],vis[66];
int n,num,m;
bool p;
int cmp(int a,int b)
{
	return a>b;
}
void dfs(int st,int cur,int cnt)
{
	if(p||cnt==num)
	{
		p=true;
		return ;
	}
	for(int i=st;i<n;i++)
	{
		if(vis[i]||cur+a[i]>m)    //訪问过的木棍或者加上当前木棍长度后超过了目标长度,则跳过本次循环
			continue;
		if(i-1&&!vis[i-1]&&a[i]==a[i-1])    //若当前木棍和上一根木棍长度同样而且上一根木棍没用到,则跳过本次循环。
			continue;
		if(a[i]+cur==m)
		{
			vis[i]=1;
			dfs(0,0,cnt+1);
			vis[i]=0;
			return;				//循环里后面的值都在dfs中求过了。这里直接返回上一层
		}
		if(a[i]+cur<m)
		{
			vis[i]=1;
			dfs(i+1,a[i]+cur,cnt);
			vis[i]=0;
			if(cur==0)           //cur为0时,直接返回上一层
				return ;
		}
	}
}
int main()
{
	while(scanf("%d",&n)!=EOF&&n)
	{
		int sum=0;
		p=false;
		memset(vis,0,sizeof(vis));
		for(int i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
			sum+=a[i];
		}
		sort(a,a+n,cmp);
		for(num=n;num>=1;num--)
		{
			if(sum%num||a[0]>sum/num)
				continue;
			m=sum/num;
			dfs(0,0,0);
			if(p)
				break;
		}
		printf("%d\n",m);
	}
	return 0;
}


版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115729.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • mavlink协议解析_jlink 串口

    mavlink协议解析_jlink 串口MAVLink是为微型飞行器MAV(MicroAirVehicle)设计的(LGPL)开源的通讯协议。是无人飞行器和地面站(GroundControlStation,GCS)之间,以及无人飞行器之间通讯常用的协议。APM、PIXHAWK飞控,MissionPlanner、QGroundControl地面站均使用了MAVLink协议进行通讯。MAVLink源码下载地址(现已更新至v2.0):https://github.com/mavlink/qgroundcontrol 用户手册:ht

  • 读《aspnetmvc-stepbystep》笔记

    读《aspnetmvc-stepbystep》笔记  读《aspnetmvc-stepbystep》笔记  这几天读了《aspnetmvc-stepbystep》,为了以后不忘记这次遇到的问题,以及此书中的一些重点观点或者主要内容,就做了一个大概的笔记。  学习软件平台:vs2008、vs2008sp1、mvc1.0rc21、传统的Web框架,如ASP/PHP/ASP.NETWebForms等等,请求的U…

  • Python 读取txt文件数据逗号为分隔符「建议收藏」

    Python 读取txt文件数据逗号为分隔符「建议收藏」fname=’./data/loc.txt’withopen(fname,’r+’,encoding=’utf-8′)asf:s=[i[:-1].split(‘,’)foriinf.readlines()]

  • bit、byte、位、字节、汉字的关系[通俗易懂]

    bit、byte、位、字节、汉字的关系[通俗易懂]字节(Byte):通常将可表示常用英文字符8位二进制称为一字节。一个英文字母(不分大小写)占一个字节的空间,一个中文汉字占两个字节的空间.符号:英文标点2占一个字节,中文标点占两个字节.1字节(Byte)=8位(bit)比特(Bit),亦称二进制位。新港台:位元比特指二进制中的一位,是二进制最小信息单位。1比特就是1位  字节    字节(Byte):字节是通过网络传

    2022年10月25日
  • LCD1602液晶使用介绍–(完整版)

    LCD1602液晶使用介绍–(完整版)lcd1602+c51介绍文章目录LCD1602介绍1602引脚信号说明控制器接口介绍1、基本操作时许2、状态字说明3、指令说明RAM地址映射控制时序图代码实现写入命令写数据试验例程CGRAM自定义字模(简易汉字显示)LCD1602介绍LCD1602液晶在实际的产品运用中也是比较多产品,应为前一段时间也正好用到了所以惊天就对LCD1602液晶做一个总结,方便以后阅读同时也希望能够帮住到需要的人,总结的可能存在错误欢迎指出!所谓的1602是指显示的时候,有2行内容每行有16个字符。其实这类字符型产

  • SSM框架——Spring+SpringMVC+Mybatis的搭建教程

    一个简单的SSM框架的搭建过程,简单易学!SSM框架在项目开发中经常使用到,相比于SSH框架,它在仅几年的开发中运用的更加广泛。

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号