竹園論壇

標題: d917 - 5. 貼磁磚 (99全國賽) [打印本頁]

作者: domen111 時間: 2014-10-20 22:50
標題: d917 - 5. 貼磁磚 (99全國賽)
本帖最後由 domen111 於 2014-11-25 16:01 編輯

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:

歡迎光臨竹園論壇 (http://forum.tfcis.org/)