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