Solution
Of course a DP problem. But the interesting thing is, this problem need Greedy at same time.
It's very easy to define DP state like:
$dp[i][0]$ means the number of days required if not upgrade position after moved to position $i$ and focus on earn money.
$dp[i][1]$ means the number of days required if we upgrade to next position.
So still very easy to find this: $dp[i][j]=dp[i-1][1]+something$。
Now, the key point is how to handle this $something$. How to handle the remain money after upgrade position? When is the best time to upgrade position?
Now it's greedy time. For each position, the upgrade is one-time. So $b[i]$ has to be paid sooner or later. Pay earlier, earn more money earlier. So if upgrade position, upgrade as soon as possible.
Then it's much more easier for us. We define $remain[i]$ as after upgraded to position $i$, the money remained.
Then the result is very clear: $$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]$$
The answer is the minimum value of $dp[i][0]$.
Code
