shunfurh 于 2017.01.16 22:40 提问
- The Lost House
One day a snail climbed up to a big tree and finally came to the end of a branch. What a different feeling to look down from such a high place he had never been to before! However, he was very tired due to the long time of climbing, and fell asleep. An unbelievable thing happened when he woke up ---- he found himself lying in a meadow and his house originally on his back disappeared! Immediately he realized that he fell off the branch when he was sleeping! He was sure that his house must still be on the branch he had been sleeping on. The snail began to climb the tree again, since he could not live without his house.
When reaching the first fork of the tree, he sadly found that he could not remember the route that he climbed before. In order to find his lovely house, the snail decided to go to the end of every branch. It was dangerous to walk without the protection of the house, so he wished to search the tree in the best way.
Fortunately, there lived many warm-hearted worms in the tree that could accurately tell the snail whether he had ever passed their places or not before he fell off.
Now our job is to help the snail. We pay most of our attention to two parts of the tree ---- the forks of the branches and the ends of the branches, which we call them key points because key events always happen there, such as choosing a path, getting the help from a worm and arriving at the house he is searching for.
Assume all worms live at key points, and all the branches between two neighboring key points have the same distance of 1. The snail is now at the first fork of the tree.
Our purpose is to find a proper route along which he can find his house as soon as possible, through the analysis of the structure of the tree and the locations of the worms. The only restriction on the route is that he must not go down from a fork until he has reached all the ends grown from this fork.
The house may be left at the end of any branches in an equal probability. We focus on the mathematical expectation of the distance the snail has to cover before arriving his house. We wish the value to be as small as possible.
As illustrated in Figure-1, the snail is at the key point 1 and his house is at a certain point among 2, 4 and 5. A worm lives at point 3, who can tell the snail whether his house is at one of point 4 and 5 or not. Therefore, the snail can choose two strategies. He can go to point 2 first. If he cannot find the house there, he should go back to point 1, and then reaches point 4 (or 5) by point 3. If still not, he has to return point 3, then go to point 5 (or 4), where he will undoubtedly find his house. In this choice, the snail covers distances of 1, 4, 6 corresponding to the circumstances under which the house is located at point 2, 4 (or 5), 5 (or 4) respectively. So the expectation value is (1 + 4 + 6) / 3 = 11 / 3. Obviously, this strategy does not make full use of the information from the worm. If the snail goes to point 3 and gets useful information from the worm first, and then chooses to go back to point 1 then towards point 2, or go to point 4 or 5 to take his chance, the distances he covers will be 2, 3, 4 corresponding to the different locations of the house. In such a strategy, the mathematical expectation will be (2 + 3 + 4) / 3 = 3, and it is the very route along which the snail should search the tree.
The input contains several sets of test data. Each set begins with a line containing one integer N, no more than 1000, which indicates the number of key points in the tree. Then follow N lines describing the N key points. For convenience, we number all the key points from 1 to N. The key point numbered with 1 is always the first fork of the tree. Other numbers may be any key points in the tree except the first fork. The i-th line in these N lines describes the key point with number i. Each line consists of one integer and one uppercase character 'Y' or 'N' separated by a single space, which represents the number of the previous key point and whether there lives a worm ('Y' means lives and 'N' means not). The previous key point means the neighboring key point in the shortest path between this key point and the key point numbered 1. In the above illustration, the previous key point of point 2 or 3 is point 1, while the previous key point of point 4 or 5 is point 3. This integer is -1 for the key point 1, means it has no previous key point. You can assume a fork has at most eight branches. The first set in the sample input describes the above illustration.
A test case of N = 0 indicates the end of input, and should not be processed.
Output one line for each set of input data. The line contains one float number with exactly four digits after the decimal point, which is the mathematical expectation value.
- caozhy 2017.01.23 23:50
- 【树状数组】PKU-2057-The Lost House
- 这里有挺完整的题解：http://blog.csdn.net/find_my_dream/article/details/4864657 题目 #include #include #include #include #include #include #include #include using namespace std; #define FRE freopen("in.txt","r
- poj-2057 The Lost House
- 题意： 给出一颗有根树，边权均为1； 一个S在根结点上，要找到在某个叶子结点上的它的房子； 有的结点上有w，可以告诉S当前结点的子树上是否有它的房子； 房子在每个叶子结点的概率相等，选择一种最佳的计划，来让S走的期望值最小；
- POJ 2057 The lost house
- 这道题求的是期望。 首先，一看到期望，就会想到可以将问题分成若干个子问题，再分开算期望，所以这道题可以使用动态规划。 注意到每个叶子有房子的概率是均等的。所以答案就是遍历每个叶子最少的步数/叶子的总数。 所以问题划归为求遍历所有叶子的最少步数。 我们令fail[x]为以x为根的子树找不到房子的最少步数。 su[x]为以x为根的子树中找到房子最少步数。 le[x]为以x为根的子树中叶子的
- 【POJ2057】The Lost House【TreeDP】
- 【题目链接】 比较经典的一道TreeDP。 因为概率是相等的，所以我们只需要计算最小步数即可，最后答案再除以叶子节点个数。 设leaf[u]表示以u为根的子树中叶子节点的个数。 设fail[u]表示以u为根的子树中，从u出发，找房子失败后，回到u点，按最优策略走的步数。 设succ[u]表示以u为根的子树中，从u出发，并成功找到房子，按最优策略走的步数。 最优策略即我们要找
- poj2057——the lost house
- 题目大意：蜗牛把壳落在一个树的叶子结点了，壳在每个叶节点的概率相同，它在根节点处开始爬，可能在树杈处遇到虫子告诉他壳是否在这个子树中，每个节点间距离为1，问他找到壳的爬行距离的最小期望 输入：（包含几个数据集） 树的结点个数n 第i个结点的父亲结点 是否有虫子（Y/N） 结点个数n为0//表示输入结束 输出：爬行距离
- POJ 2057 The Lost House
- 树形DP的第一题，看了好几天才明白.... 题目大意： 有一只蜗牛爬上某个树枝末睡着之后从树上掉下来,发现后面的"房子"却丢在了树上面, 现在这只蜗牛要求寻找它的房子,它又得从树根开始爬起去找房子。现在要求一条路径使得其找到房子所要爬行的期望距离最小。 解题思路： 影响期望的因素有树的结构，分支节点上是否有虫子，蜗牛走的路线。 对于任意一棵子树来说树的结构，分支节点上是否
- poj 2057 The Lost House
- 论文题，树dp多说两句，这个题的决策是在一个节点时选择子节点遍历的顺序通过贪心来优化dp#include<cstring> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> using namespace std;const int maxn = 1123;vector<int> edge[maxn];vo
- pku2057 The Lost House
- <br /> <br />一个N（N<=1000）个节点树上，树最多是八叉。有一个蜗牛把壳丢在了某个叶子节点。它从根节点出发沿树枝走去找壳。某些内点上有蚜虫，会告诉你下面叶子上是否有壳。为蜗牛找决定一个路径，使蜗牛找到壳的路径长度的期望值最小值，即所有可能的路径长度和的平均值。<br /> <br /> <br />这道题比较经典，首先对于每一个以i为根的子树，记b[i]为在以i为根的子树中找没有找到的时候所经历的路径长度（包括从父亲到他的边），以f[i]表示在以i为根的子树中找到的期望步数，以s[i]表示
- POJ 2057 The Lost House 树形DP+贪心
- 最近一直在做树形dp，感觉这道题出的非常不错。卡了我一天。。 一上来读完题感觉和dp的思路很像，但是自己太弱了，无从下手。于是各种百度看结题报告、看论文。推荐几个结题报告 http://hi.baidu.com/zhymaoiing/blog/item/1aa0e1ccf1bc0d1b01e9288a.html http://blog.sina.com.cn/s/blog_
- 【Poj 2507】The Lost House（树型dp）
- 【Poj 2507】The Lost House（树型dp） Time Limit: 3000MS Memory Limit: 30000K Total Submissions: 2457 Accepted: 1020 Description One day a snail climbed up to a big tree and f