d917 - 5. 貼磁磚 (99全國賽)

domen111

http://zerojudge.tw/ShowProblem?problemid=d917

感謝學長的提示「兩個方向的最佳解會不會衝突」，發這篇文讓我自己記一下是怎麼證明最佳解不會衝突的。
做法: 算出兩個方向拓樸深度，相乘就是答案 (當然還要再乘上w*w)
說明:
如圖，黑色代表直向的邊，深度為4，3號、4號、5號在同一層。題目寫說有n(n-1)/2條邊，所以每個點之間一定會存在一條邊。
3、4、5號在同一層 => 3,4,5號之間不可能會有直向的邊 => 3,4,5號之間一定都是橫向的邊 => 3,4,5號之間在橫向時因為之間互相有邊所以不可能在同一層 => 直向層數最少時並不會造成橫向層數增加 => 兩個方向的最佳解不會衝突



隨便寫拓樸排序的AC code:

遊客，如果您要查看本帖隱藏內容請回復