首页 > 其他分享 >7.19

7.19

时间:2023-07-19 20:11:34浏览次数:50  
标签:剪枝 排列 int 7.19 搜索 include

搜索

DFS

就是通过递归来搜索,枚举所有情况来求解。
搜索相对于多个for循环嵌套来说肯定效率更高,在数据会很大时更容易实现,但有时避免不了TLE,所以需要进行优化:

剪枝

1.最优性剪枝 再求解时如果当前情况比已知的解差,或无法优于已知解,然后return,所以就可以先搜索容易成为最优解的方案,避免去搜索较差的解。
2.可行性剪枝 就是当前情况不可行就return。

记忆化搜索

就是将已经计算出来的结果保存起来,当之后的计算用到的时候直接取出结果,避免重复运算,因此极大的提高了效率。

例题:

Luogu 1706 全排列问题

题目描述
按照字典序输出自然数1到n所有不重复的排列,即n 的全排列,要求所产生的任一数字序列中不允许出现重复的数字。

注释及代码:

#include<bits/stdc++.h>
using namespace std;
int n;
bool st[10];//标记每个数是否用过 
int path[10];//用来记录答案 
void  dfs(int step)
{
	if(step==n+1)//有n个数时输出 
	{
		
		for(int i=1;i<=n;i++)
		{
			cout<<setw(5)<<path[i];//setw(5)能输出时每个数的长度为5; 
		}
		cout<<endl;
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(st[i]==0)//如果没被用过 
		{
			st[i]=1;//先标记一下,防止重复 
			path[step]=i;//记录答案 
			dfs(step+1);//进入下一次递归 
			st[i]=0;//再把它标记为未被用,也就是回溯操作 
		}
	}
} 
int main()
{
	cin>>n;
	dfs(1);
}

以上为通过搜索实现的代码,但强大的c++有个next_permutation函数,它能把当前的排列直接变成下一个字典序,但仅在全排列中有用,以下是其应用:

#include<bits/stdc++.h>
using namespace std;
int a[1000];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) a[i]=i;
	do{
		for(int i=1;i<=n;i++) cout<<setw(5)<<a[i];
		cout<<endl;
	}while(next_permutation(a+1,a+n+1));
}

标签:剪枝,排列,int,7.19,搜索,include
From: https://www.cnblogs.com/Glw-/p/17566610.html

相关文章

  • day83(2023.7.19)
    1.使用SqlSession操作数据库 2.Mapper动态代理原理3. MyBatis新增 运行结果:4.MyBatis修改没优化前: 优化后:(只需写一次就ok了) 运行结果:4.MyBatis删除、根据Id查询 运行结果: 5.根据ID查询用户和运行结......
  • 7.19-分摸 一枪2模(09案例分析)包括 分模-做虎口-做摸胚
      ......
  • 7.19-分模(接着上午那个案例 只不过多了开框,打螺丝,管理图层,顶针(丝筒针)中托司)这几个功能
    开框开在上下模核心的产品框位置(不开框的话打螺丝会穿透上下模的位置)正常情况下打螺丝会在上模框的位置打打在模仁位置的一半位置而不是直接打穿切记开框之后要移除参数螺丝打在上下模虎口的位置 ......
  • 7.19考试总结
    总结这次考试,我发现了几个问题。dp状态和转移方程写不出。看出了是dp却不知道如何去实现。平时的思考不够细致认真。数据的范围没有看清。计划接下来的一个月重点突破dp学习多种dp熟练动态转移方程和状态。 ......
  • Day12(2023.07.19)
    行程9:00到达上海电气集团数字科技有限公司(闵行区合川路2555号2号楼)9:30  听老师与公司负责人交谈11:30--13:00   吃饭休息13:30  听老师与公司负责人交谈15:00         实践windows安全检测16:30     ......
  • 集训游记 7.19-7.20 图论
    最小生成树MSTP5994[PA2014]Kuglarz考虑连边\(i,j\)表示花费代价知道区间\([i,j)\)的奇偶性.容易发现\(i,j\)联通就可以发现表示出\([i,j)\).考虑最终局面,一定要推出每个\([i,i+1)\)的奇偶性.要求每对\([i,i+1)\)联通.即整张图联通.最小生成树k条白边最小生成树......
  • 7.19总结
    上午起的比较早,五点半起来了,吃了饭去姥姥家一趟,回来后在床上躺了会,看了一下假期前老师发的那个java测试题,大约读了一遍,了解了一下功能需求,其实对于目前的我的来说,感觉还是有些难,希望小学期做完那几个程序系统会给我带来点提升吧。下午就摆了,看了会大道至简,里面有些看不懂,反正今天......
  • iOS企业签名掉签,iOS企业签名掉签了怎么办?103.107.190.x
    不能上架到AppStore的iOS应用,几乎每一个开发者的选择都是通过iOS签名这种内测渠道来完成APP的上架任务,最常用的就是企业签名、超级签名以及TF上架,其中最受欢迎的当属于企业签名了。不过企业签名会出现掉签的现象,那么企业签名掉签了该如何处理呢?今天我就来分享下关于签名掉签的原......
  • 安装confluence7.19.4、jira9.4破解并使用Nginx代理
    背景略安装jira准备两个目录,一个是jira的安装目录,一个是jira的home目录,数据都存在home目录/data/jira/data/jira_home下载,解压wgethttps://product-downl......
  • 《安富莱嵌入式周报》第222期:2021.07.19--2021.07.25
    是德科技(安捷伦)分享的示波器知识普及,80页PPT,动图讲解。内容做的非常好,很多都是动图说明。​​High-Speed_Oscilloscope_Fundamentals.pptx​​(102.07MB)   网上搜集......