Codeforces Round #713 Education DP+贪心

题意

你要凑$c$块钱。有$n$个级别的工可以打。对于级别为$x$的工作,一天的收入为$a[x]$。且级别越高的工作收入一定越高。现在从$x$升级到$x+1$的工作,需要花$b[x]$元升级。升级要占用一整天去学习。

现在问你最短要几天才能凑够$c$块钱。

题解

一看就是dp。但有趣的是,这个题同时还要贪心。

很容易想到这样定义状态:$dp[i][0]$表示级别$i$的工作后不再升级,专心打工挣钱需要凑够钱的天数。$dp[i][1]$表示级别$i$后,我凑够下一级学费需要的天数。很容易想到$dp[i][j]=dp[i-1][1]+something$。

而这个$something$最以来的就是升级之后剩下的钱怎么处理?什么时候升级是最优的?

这个时候我们就要贪心了。可以注意到,升级是一次性的。也就是$b[i]$块的学费早晚都得交,早交早领高工资。如果要学,那么一定是尽早学。

于是就简单多了,我们维护一个$remain[i]$。表示学到第$i$级之后,剩下多少钱。

于是立刻就有:$$dp[i][0]=dp[i-1][1]+\lceil{\frac{c-remain[i]}{a[i]}}\rceil$$$$dp[i][1]=dp[i-1][1]+\lceil{\frac{b[i]-remain[i]}{a[i]}}\rceil+1$$$$remain[i+1]=remain[i]+ a[i]\cdot{\lceil{\frac{b[i]-remain[i]}{a[i]}}\rceil} - b[i]$$。

最后的答案就是$dp[i][0]$的最小值。

代码

Submission #112545505 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论