XShell matlab Apache Pivot教程 events plugins vbscript Uploadify float占几个字节 matlab复数求模 mysql转字符串 plsql连接mysql数据库 python算法 python代码 python打开文件夹 java取当前时间 java获取 刷机工具下载 路由器有没有辐射 美国地址生成器 fdisk下载 ABViewer 数独软件 ps蒙版抠图详细教程 奥法隐藏外观 c程序 分屏软件 ipad上市时间 android下载文件 ps反选 黑域怎么用 debian安装教程 下拉框默认选中 图片格式太大怎么变小 xmlhttp c语言小程序 双通道内存有什么好处 js动画效果 东方通达信 dnf搬砖tar打包 kk直播精灵
当前位置: 首页 > 学习教程  > 编程语言

专题I_E个人解题报告-DFS

2021/1/13 20:27:31 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

I_E题(dfs)POJ-1011 Sticks UVA-307 Sticks 是的我又跑去学递归了QAQ 这个题最好到UVA-307去交题 (好像是说POJ-1011的数据太水) 题意 乔治拿了相同长度的木棍,随机切开,直到所有零件的长度最大为50个单位。 现在,他想…

I_E题(dfs)POJ-1011 Sticks UVA-307 Sticks
是的我又跑去学递归了QAQ

这个题最好到UVA-307去交题 (好像是说POJ-1011的数据太水)

题意
乔治拿了相同长度的木棍,随机切开,直到所有零件的长度最大为50个单位。 现在,他想将木棍恢复到原始状态,但是他忘记了原来拥有多少木棍以及它们原本有多长。 请帮助他,设计一个程序,计算出那些棍子的可能的原始最小长度。 所有以单位表示的长度都是大于零的整数。
输入
输入包含2行。 第一行包含切割后的木棍零件数量,最多为64个木棍。 第二行包含被空格隔开的那些部分的长度。 文件的最后一行包含零。
输出
输出应包含原始木棍的最小长度,每行一根。
Sample Input
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
Sample Output
6
5

题意: ·····恢复到原来的多根相同的木棍(或只有一根),求原来的木棍长度的最小值。

分析:
设 切开后木棍所有长度 为一个数组 a ,所有的长度和为sum 。(此后的 每一组 表示的是 原状态的每一根木棍的长度
原状态的木棍长度只可能是 [ 数组中的最大值,sum ] 之间能整除sum的数,求最小值就从 这些能整除sum的 的第一个数开始 依次判断该长度x是否满足条件 如满足则原始长度的最小值就是x
(此处满足条件就是:恰好 (即所有木棍都用组合完了) 构成了 num(num=sum/x) 根长度为x的木棍)

第一步:将所给数据降序排序
第二步:构造dfs函数判断长度x是否满足条件

dfs函数中提前结束返回0 的情况: ( 以下的满足条件均表示: 当前组 的总长度 为 x)

  1. 对于 当前组 满足条件 但是 下一组 不满足条件。
  2. 对于 当前组 不满足条件:对于 当前组 第一个(其为该组的最长的) 不满足条件 {这就是前面为什么要降序排序的原因: 当前组 的最长的都找不到能构成x的解 (简单说就是 加上了数组中每个没用过的数 长度都达不到 x), 那就不用说比它小的还能找到解}

AC代码

//注意:在UVA上提交的话 不要用c++的输入输出 用c的输入输出才没超时;POJ的话没试过
//#include <bits/stdc++.h>//POJ上用这个我不知道为什么编译错误
#include <iostream>
#include <algorithm>
#include <string.h>//memset()头文件
using namespace std;

int n,sum,x,num;
int a[70],v[70];
bool cmp(int &a,int &b){return a>b;}

bool dfs(int cnt,int len,int cntnum){//cnt-当前组的第几根,cntnum-到了第几组,len-当前组的长度
	if(cntnum==num)return 1;//枚举所有木棍有解( 构成了num根均为长度x的木棍)
	
	for(int i=cnt;i<n;i++){
		if(v[i] ||( i && !v[i-1] && a[i]==a[i-1]) )continue;//若该木棍被用过 或 该木棍跟前一根木棍一样且前一根没用过 就跳过
		
		if(len+a[i]==x){
			v[i]=1;
			if(dfs(0,0,cntnum+1))return 1;
			v[i]=0;
			return 0;//提前结束情况1
		}
		else if(len+a[i]<x){
			v[i]=1;
			if(dfs(i+1,len+a[i],cntnum))return 1;
			v[i]=0;
			if(len==0)return 0;//提前结束情况2;此处改成 if(cnt==0)return 0; 也可以 只是在UVA中提交就多了10ms
		}
	}
	return 0;//枚举所有木棍都没得到解,返回0
}
int main(){
	while(scanf("%d",&n)){
		if(n==0)break;
		sum=0;
		memset(a,0,n);//可加可不加 有时候不加也过 多组数据 以防万一都加上了
		for(int i=0;i<n;i++){scanf("%d",&a[i]);sum+=a[i];}
		
		sort(a,a+n,cmp);
		for(x=a[0];x<=sum;x++){//一定要注意
			if(sum%x==0){
				num=sum/x;//num为原来木棍根数
				memset(v,0,sizeof(v));
				if(dfs(0,0,0)){break;}
			}
		}
		printf("%d\n",x);
	}
	return 0;
}

本文链接: http://www.dtmao.cc/news_show_600318.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?