題目傳送門：https://www.luogu.com.cn/problem/P9123

本題用到的算法是線性 DP。

對于第??天，只有一種選擇——買票，當天花費為 。

對于第 ?天，有兩種選擇：

• 買票，當天花費為 ；

• 不買票，當天花費為 。

我們設(shè) ?為前 ?天的花費總和，遞推式如下：

• 若 ，則 ；

• 若 ，則 。

最后輸出 ?即可。