木棍游戏 深度优先搜索
2022/1/13 23:03:48
本文主要是介绍木棍游戏 深度优先搜索,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
给出 nnn 根长度不一的木棍,第 iii 根棍子长度为 aia_iai 。两根长度分别为 aba_bab 和 aca_cac 的木棍可以拼接成一根长度为 ab+aca_b+a_cab+ac 的木棍,同理 333 根, 444 根,甚至 nnn 根都能拼接。
问:使用这 nnn 根木棍作三角形的边(一根木棍至多使用一次,也可以不使用),能拼出的面积最大的三角形的面积。
输入描述:
第一行包含一个整数 nnn (3≤n≤8)(3 \le n \le 8)(3≤n≤8),表示木棍的数量。
第二行包含 nnn 个整数,用空格隔开,表示 nnn 根木棍的分别长度 a1,a2,...,ana_1,a_2,...,a_na1,a2,...,an 其中 1≤ai≤1e31\le a_i\le 1e31≤ai≤1e3。
输出描述:
输出一行,表示能拼出来的最大三角形的面积,结果保留一位小数。如果无法拼出三角形,输出−1-1−1。
示例1
输入
3 3 4 5
输出
6.0
示例2
输入
3 3 4 7
输出
-1
这一题似乎不太能贪心,规律并不好找,但是因为数据量很小,就采用最暴力的方法,用搜索来解决
可以看出一个木棍有四种状态,在第一条边,第二条边,第三条边,不在任何一条边,这里就把a,b,c当做三角形的第1,2,3条边,dfs搜索以下边为参数,向前走一直走到没有元素为止,这个时候判断一下三角形是否合法并更新ans就可以
有一些小细节就写在程序里了
#include<stdio.h> #include<algorithm> #include<math.h> using namespace std; int xx[1000]; int a, b, c; int n; double ans=-1; double s(int a, int b,int c) { double p = (a + b + c) / 2; return sqrt(p*(p-a)*(p-b)*(p-c)); } void dfs(int x) { if (x > n)//枚举超出了数组,代表所有的数都有了位置, { if (a < b + c && b < a + c && c < a + b)//满足条件 { //printf("%d %d %d\n",a,b,c); ans = max(ans, s(a, b, c)); return; } else return; } //接下来搜索四种状态-->a[x]不放,放第一二三条边, ;//直接跳过这个数 dfs(x + 1); a +=xx[x];//第一条边 dfs(x + 1); a -= xx[x]; b += xx[x];//放第二条边 dfs(x + 1); b -= xx[x]; c += xx[x];//第三跳 dfs(x + 1); c-=xx[x];//最后一步取出来的操作不能忘记 } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", xx + i); dfs(1); if (ans == -1)printf("-1\n"); else printf("%.1lf\n", ans); return 0; }
这篇关于木棍游戏 深度优先搜索的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现