POJ-1062 解题报告

题意简述

你想娶酋长的女儿,但酋长要求你给一定数额金钱的聘礼。除了金钱外,酋长也允许你用部落里其他人的某物品加上一点钱作为聘礼。而其他人的物品也可以通过指定的另外一些人的某物品加上一些金钱获得。部落里的每个人有一个等级。你的整个交易过程涉及的人的等级只能在一个限定的差值内。问你最少需要多少金钱才能娶到酋长女儿。假定每个人只有一个物品。

例:

最高最低等级差不超过1,共4个物品

酋长的女儿    等级3     要求现金10000元     或甲的物品+8000元     或乙的物品+5000元

甲的物品        等级2     要求现金1000元        或丙的物品+200元

乙的物品        等级2     要求现金3000元        或丙的物品+200元

丙的物品        等级2      要求现金50元

在这个例子中,最少花费方案是:买丙的东西(50)换乙的东西(+200)换酋长女儿(+5000)一共5250元。

Continue reading “POJ-1062 解题报告”

POJ-2253 解题报告

题意简述

湖中有N(2<=N<=200)块石头,标号从1到N。青蛙1在石头1上,青蛙2在石头2上。给定所有的石头坐标。青蛙1试图从石头1到石头2来找青蛙2,它可以经由任意石头组成的路径。在所有可能路径中找出一条路径,使其中最长的一步的长度小于其他路径中最长的一步的长度。

本题可以化简为,点1与点2间存在若干条路径,每条路径中都存在最长的一条边。找出一条路径使得该路径最长边的长度小于其他任意路径最长边。

Continue reading “POJ-2253 解题报告”