CSP-S 2021 廊橋配置設定

【題意】

​​題目連結​​

【分析】

很顯然，如果我們能夠求出f[0...N]和g[0...N]分别表示國内/外有i個停機坪時，最多的停靠飛機數量，那麼max{f[i]+g[n-i]}就是答案

現在考慮如何取求f和g

我們考慮每次貪心的把新的一架飛機停在編号盡可能小的停機坪上，這樣我們從前到後走一遍，借助優先級隊列即可算出f和g

看看代碼就很清晰了

【代碼】