HBC223807[NOI1998]免费馅饼,线性dp,动态规划TheBoomsdayProject题解

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

Aloha is a poor guy who likes riding a bike. But he is too poor to afford a bicycle. Recently, the Boom's bike-sharing service entered his school. It only costs r{r}r yuan for every single rent of

Aloha is a poor guy who likes riding a bike. But he is too poor to afford a bicycle. Recently, the Boom's bike-sharing service entered his school. It only costs r{r}r yuan for every single rent of a bicycle. From then on, Aloha could rent a bike and enjoy the speed and passion of riding. The Boom's company has launched a promotion program named the BoomsdayProject{Boomsday Project}BoomsdayProject. In this program, users can buy discount cards with several free rents and a valid period. For example, after purchasing a discount card with k{k}k free rents and d{d}d days of valid time, one doesn't need to pay extra fees for the following k{k}k rents in the next d{d}d days. Note that, no matter when the card is bought on day t{t}t, it will always expire at the end of day t+d−1{t+d-1}t+d−1. Also, any new discount card overrides the previous one even if it is still valid, i.e., the remaining free rents of the previous discount card are voided immediately when the new discount card is purchased. There are n{n}n different types of discount cards in the BoomsdayProject{Boomsday Project}BoomsdayProject. A card of i{i}ith type with kik_iki​ free rents and a valid period of di{d_i}di​ days costs cic_ici​ yuan. One can buy any type of discount card unlimited times. Given the rental records, Aloha wants to know the minimum money he has to pay, provided that he takes the best strategy.

标签： HBC223807[NOI1998]免费馅饼 线性dp 动态规划TheBoomsdayProject题解