木棍游戏 深度优先搜索
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-12-26JavaScript入门教程:从零开始学习JavaScript编程
- 2024-12-26JavaScript入门教程:从零开始学习JavaScript
- 2024-12-26JS编程入门指南:从零开始学习JavaScript
- 2024-12-25Java编程面试题详解与解答
- 2024-12-25TS基础知识详解:初学者必看教程
- 2024-12-252024面试题解析与攻略:从零开始的面试准备指南
- 2024-12-25数据结构与算法学习:新手入门教程
- 2024-12-25初学者必备:订单系统资料详解与实操教程
- 2024-12-24内网穿透资料入门教程
- 2024-12-24微服务资料入门指南