查看: 621|回復: 0

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

[複製鏈接]
  • TA的每日心情
    開心
    2015-4-12 10:09
  • 簽到天數: 137 天

    [LV.7]常住居民III

    142

    主題

    686

    帖子

    3559

    積分

    邁向天堂

    蘇多門

    Rank: 8Rank: 8

    積分
    3559

    新手達陣台南一中資訊社程式設計達人 - 2014

    發表於 2014-10-20 22:50:41 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    x
    本帖最後由 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:
    遊客,如果您要查看本帖隱藏內容請回復
    蘇多門 domen111
    My Web: https://sites.google.com/site/domenprg/
    回復

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表