题目
由于是01年的题目
难度自然比较低
前3题都是搜索/模拟题 在这里就不多累述
第4题一开始被他数据小的特点蒙骗了
搜索|状态压缩的DP 好像都不行 一时间没了头绪
后来想到了二分图 其实早应该想到二分图
以横向为例 显然对于每一条线段 如果线段上没有"墙" 则线段上对多只能有1个车
纵向同理
所以先遍历一次这个矩形 求出所有上述线段 以及所有非墙格子所在的横纵线段
将所有有相交的线段之间连一条边 求二分图最大匹配即可
对于某些所求为XX最多 每个XX影响两个元素的题目 二分图往往能够起到作用
posted on 2009-03-12 22:54
250 阅读(1103)
评论(0) 编辑 收藏 引用 所属分类:
oi