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