Readme

1187.Make-Array-Strictly-Increasing

考虑到本题给予了一种替换操作的“权力”，从动态规划的套路经验可以尝试，以使用这种“权力”的次数作为状态。因此我们设计dp[i][k]表示：如果我们可以使用k次替换操作使得前i个元素严格递增，此时第i个元素可以选择的最小值。注意，这个dp状态变量的“值”的定义和我们以往套路不同的地方在于，并没有照搬题目的问题"minimum operations"，因为操作数已经用dp的下标k标示了。我们之所以选择“此时第i个元素可以选择的最小值”作为值，是有点贪心的思想。因为我们想要使得这个递增序列能够接的更长的话，必然会让第i个元素尽可能地小。

我们如何更新dp[i][k]呢，显然突破口就在于第i个元素是否使用替换操作的“权力”。

如果第i个元素我们不替换。那么显然要求前i-1个元素用k次操作已经保持递增，并且arr1[i]能够顺利地再接上去。即

if (arr1[i] > dp[i-1][k])
  dp[i][k] = arr1[i]

如果第i个元素我们做了替换。那么显然要求前i-1个元素用k-1次操作已经保持递增，并且能把arr1[i]替换后的数再顺利地再接上去。那么我们想替换成什么数呢？显然应该是arr2里面恰好比dp[i-1][k-1]大一点点的那个数。注意下面的代码只在k>=1的时候有效。

auto iter = upper_bound(arr2.begin(), arr2.end(), dp[i-1][k-1]);
if (iter!=arr2.end()) 
  dp[i][k] = *iter; 

以上两种情况都需要考虑。因此我们是用两个值来试图更新dp[i][k]，取较小的那个。如果两种情况都无法满足，即都无法更新dp[i][k]，那么我们会默认dp[i][k]为无穷大，表示“我们无法使用k次替换操作使得前i个元素严格递增”。