web analytics

uva10603 解题报告

uva10603 Fill 倒水问题 解题报告:

题目链接:https://uva.onlinejudge.org/external/106/10603.pdf

题目大意:

设3个杯子的容量为abc,起初只有第三个杯子装满了c升水。其它两个杯子均为空。最少要倒多少升水可以让某一个杯子里有d升水。如果无法做到d升水。就让某个杯子里有d‘升水,其中d’

分析:

这个样子其实有一点点动态规划的味道,其实不是。一看到这种求最小的倒水量。第一眼就应该想到用BFS。广搜,可以完美的设计到这种状态或者是抉择问题。而这道题。3个杯子,假设在某一时刻第一个杯子里有v1升水。第二个杯子有v2升水,第三个杯子有v3升水。而这个时候可以说是在某一时刻的状态。“状态”这个名词很玄学,往往有很多的算法和思想都会运用到状态这个概念。而每个状态之间都可以通过某种方式进行转换,这道题就是通过倒水。

 

循环来两,两倒水,倒出后的结果放到一个新的状态,新的状态进队。(进队之前要判重。)理论上就有 (a+1)(b+1)(c+1)=8120601种状态,这个状态有点多。内存有点多。但是呢,这种判断是不精确的。因为,水就那么多。当a,b的量确定之后,c的量就确定了,所以这么大的状态就一下缩小到201^2=40401;这就小多了。

而在一般的BFS中目标状态最先搜索到的一定是步骤最小的一个目标状态,而这道题求的不是最小步骤的目标状态而是倒水量最小的目标状态,所以,这里的队列应该用到优先队列,优先队列里的判断条件就是根据每种状态的倒水量的大小,来判断。

 

 

Post a Comment

You must be logged in to post a comment.