题意
你要凑$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
