CodeForces-500C

傳送門

給n本不同重量的一摞書編號1～n。給定m次操作。操作b代表花費標號為b的書上方其他書的重量總和，將書b位移到這疊書的最上方。問初始書應該如何疊放，才能使m次操作后總花費最小

輸入 n本書 m次操作

?? ? ? n個數 書的重量

m個數 操作對象

輸出 總花費

?

題解：我們先考慮每本書讀不超過一次。首先就會想到最后哪本書是在最上面是確定的，貪心地考慮最后一步的花費最小，那么這本書應該放在最上方。可上一步的操作已經確定了哪本書目前處于最上方，所以最后這本書最好的情況是處于上方第二本。之后我們將這兩本書看成一本，重復上述看待問題的過程，就可以得出書的排放順序應該與書第一次出現的順序相同。由于每本書的花費只與它上方的書的重量相關，它下方的書如何擺放不影響結果，所以我們這樣對下方的書的排列貪心求解，遞歸回去，得到的答案一定是正確的。在考慮一本書出現多次是否情況有變。當一本書第二次出現，兩次出現之間的書的重量一定對答案有貢獻，如果我們改變這本書的初始位置，只會增大對這本書第一次操作的花費，顯然只會使答案變大。

總之，我們利用的就是第j次操作時，前面j - 1次操作的書必然在其上方，無論這本書處于哪個位置，前j-1次操作的書的重量都一定對答案有貢獻。所以這個貪心沒有后效性。記錄每本書第一次出現的時間就好了。沒有出現的書按任意順序擺放即可