首页 / JAVA / HDOJ-ACM1011(JAVA)

HDOJ-ACM1011(JAVA)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了HDOJ-ACM1011(JAVA)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1537字，纯文字阅读大概需要3分钟。

内容图文

转载声明：原文转自：http://www.cnblogs.com/xiezie/p/5569721.html

技术分享

 

搞懂题意之后，个人感觉，这道题题目的描述相当的费解~ 

 

做这道题目，个人感觉，涉及到树的遍历（深度搜索）、动态规划的知识点。 

 

由于网上找不到什么好的问题解释，我把自己的翻译放上来了。

问题描述：
　　你是星河战队的领袖，被派来摧毁的虫子基地。基地建在地下。它实际上是一个巨大的洞穴，它包括许多与隧道相连的房间。每个房间都被一些虫子所占据，他们的大脑藏在一些房间里。科学家刚刚研制出了一种新武器，想要在一些大脑中进行实验。你的任务是摧毁整个基地，捕捉尽可能多的大脑。
　　杀死所有的害虫总是比捕捉他们的领头容易。为你提供了一张地图，上面标记了所有的房间内的害虫的数量以及存在一个领头的可能性。洞穴的结构就像一棵树——从入口开始仅有一条路径通向每个房间。为了尽快结束战斗，你不想等待士兵就推进到下一个房间，你必须留下一些士兵在每个房间抗击所有里面的害虫。他们曾经去过的房间不再进入。
　　一个士兵可以杀死20害虫。因为你没有足够的士兵，你只能选择进入一些房间，其他的工作让神经毒气做。同时，你应该最大限度地提高捕捉一个大脑的可能性。为了简化这个问题，你只要最大限度地提高对所取房间的所有可能性的总和。制定这样的计划是一项艰巨的工作。你需要电脑的帮助。
输入：
　　两个数（正整数）：
　　　　N：房间数
　　　　M：士兵数

　　N*2个数（非负整数）：
　　　　a: 害虫的个数
　　　　b： 存在一个领头的可能性（百分比）
　　（N-1）*2个数（整数）：
　　　　c: 入口号
　　　　d： 通向哪个房间

　　　　如：上述的第一种输入（如图描述）

技术分享

这道题给人最大的迷惑是二叉树，实际上的树形结构

以下是我写的测试输入：

6 10 50 10 40 10 40 20 65 30 70 30 100 50 1 2 1 3 2 4 2 5 3 6
-----------80//输出结果

1 1 20 7
-----------7

5 10 50 10 40 10 40 20 65 30 70 30 1 2 1 3 2 4 2 5
-----------50

7 10 50 10 40 10 40 20 65 30 70 30 100 50 20 60 1 2 1 3 2 4 2 5 3 6 4 7
-----------110

7 10 50 10 40 10 40 20 65 30 70 30 100 50 20 50 1 2 1 3 2 4 2 5 3 6 5 7
-----------100

8 10 50 10 40 10 40 20 65 30 70 30 100 50 20 50 80 80 1 2 1 3 2 4 2 5 3 6 5 7 3 8
-----------110

17 10 50 10 40 10 40 20 65 30 20 30 80 50 20 50 60 80 20 10 20 50 20 60 20 40 20 10 20 70 20 80 20 140 20 150 1 2 1 3 2 4 2 5 3 6 5 7 3 8 8 9 6 10 6 11 8 12 12 13 7 14 7 15 4 16 4 17
-----------200

4 2 1 1 1 2 1 3 1 4 1 2 1 3 1 4
-------5

5 3 1 1 1 2 1 3 1 4 1 5 1 2 1 3 1 4 3 5
-------9

提交了N次，一直WA，未AC状态。。。

原文：http://www.cnblogs.com/xiezie/p/5569721.html

内容总结

以上是互联网集市为您收集整理的HDOJ-ACM1011(JAVA)全部内容，希望文章能够帮你解决HDOJ-ACM1011(JAVA)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

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

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1259514.html

来源：【匿名】