題目
由于是01年的題目
難度自然比較低
前3題都是搜索/模擬題 在這里就不多累述
第4題一開始被他數據小的特點蒙騙了
搜索|狀態壓縮的DP 好像都不行 一時間沒了頭緒
后來想到了二分圖 其實早應該想到二分圖
以橫向為例 顯然對于每一條線段 如果線段上沒有"墻" 則線段上對多只能有1個車
縱向同理
所以先遍歷一次這個矩形 求出所有上述線段 以及所有非墻格子所在的橫縱線段
將所有有相交的線段之間連一條邊 求二分圖最大匹配即可
對于某些所求為XX最多 每個XX影響兩個元素的題目 二分圖往往能夠起到作用
posted on 2009-03-12 22:54
250 閱讀(1141)
評論(0) 編輯 收藏 引用 所屬分類:
oi