Posted on 2009-03-03 23:22
hello_world 阅读(1228)
评论(0) 编辑 收藏 引用
Waterloo local 2002.09.21
Trains |
DP，图论 |
| |
|
| Square |
搜索 |
| Blocks |
暴力 |
Faucet Flow
|
|
Trains：(==)
Square：
这道搜索题与pku1011有相似的解法，剪枝都一样的，关于1011已经很经典了
http://www.acrush.cn/?cat=9这里有很详细的剪枝！基本上改改就能过了~！
blocks：暴力加个界能跑0ms
这道题类似
Grocery store Faucet Flow
这是一道很优美的题，推荐
首先我们来判断一下水到底会从左边漏还是从右边漏，假设左边最高的高度是p， 右边最高的高度是q
若p > q 流往右边
若p < q 流往左边
若p==q 那就要看那边能装下更多的水
前两种那块最高的挡板不可逾越，想想就会明白，后一种水流会分成两股，左右等量，那就要看那边坚持的久了
大概意思就是这样，考点就是可能会有相等高度的挡板，这无疑加大难度，此题的具体实现也需要费些功夫。
再推荐一道类似的题，说类似只是背景类似，解法各异，后一种的代码实现方法也是很不错的
Artificial Lake