CF1684 D. Traps

題目說明

存在從 1 至 n 共 n 個陷阱，你必須依照順序經過這些陷阱。第 i-th 個陷阱，將會造成 ai 點基礎傷害給你。

與其從頭走過每個陷阱到尾，你可以跳過其中一些陷阱，但你不得跳過多於 k 個陷阱。如果你跳過一個陷阱，陷阱將不會對你造成任何傷害。但是有一個額外規則，如果你跳過一個陷阱，之後的每一個陷阱其傷害都會增加 1 (這是額外傷害)。

注意如果你跳過一個陷阱，你不會承受任何傷害(不管是基礎傷害還是額外傷害)。還有，額外傷害是會疊加的，例如你走過陷阱 i 時曾跳過三個陷阱，你將會得到 ai + 3 點傷害。

你必須找到在不跳過多於 k 個陷阱的可能最低傷害。

思路

我看到這個題目的第一直覺是：這是一個動態規劃題目。而結果告訴我，其實這是一個貪婪問題，筆者的朋友看到也直覺是貪婪問題，我想這就是經驗的差距。在比賽中我是有用動態規劃通過基本測資的，我們就來看一下做法。

int solve(const vector<int>& dmgs, int k) {
  const int len = dmgs.size();
  vector<vector<int>> dp(k + 1, vector<int>(len, INT_MAX));
  dp[0][0] = dmgs[0];
  for (int i = 1; i <= k; ++i) {
    dp[i][0] = 0;
  }

  for (int i = 1; i < len; ++i) {
    int dmg = dmgs[i];
    dp[0][i] = dp[0][i - 1] + dmg;
    for (int j = 1; j <= k; ++j) {
      dp[j][i] = min(dp[j - 1][i - 1], dp[j][i - 1] + dmg + j);
    }
  }
  return max(dp[k][len - 1], 0);
}

然而這個做法並沒有辦法通過第二組測資，筆者在比賽中左思右想就是想不出為什麼，還一度懷疑是演算法錯誤。後來強者我朋友提醒我，其實是整數型別大小不夠，所以修正以後就能通過第二組測資，但是這樣不代表就解了這個題目，事實上動態規劃並不是一個最佳解，尤其是在 k 數特別大的狀況下，時間複雜度為 k * n。所以 k 太大，以動態規劃解法是會造成 TLE 的。

int64_t solve(const vector<int>& dmgs, int k) {
  const int len = dmgs.size();
  if (k >= len)
    return 0;
  vector<int> avoid_dmgs(len);
  int64_t ans = 0;
  for (int i = 0; i < len; ++i) {
    ans += dmgs[i];
    avoid_dmgs[i] = dmgs[i] + i + 1;
  }
  sort(STDALL(avoid_dmgs), std::greater<int>());
  ans -= accumulate(begin(avoid_dmgs), begin(avoid_dmgs) + k, int64_t(0));
  for (int i = 0; i < k; ++i) {
    ans += len;
    ans -= i;
  }
  return ans;
}

貪婪演算法的解法，是先算出在不跳過任何陷阱的狀況下，我們會獲得多少傷害。接著再計算，如果我們跳過這些陷阱能避開多少傷害，結果存在 avoid_dmgs 中。這裡寫為 dmgs[i] + i + 1 的理由， i 是代表在此陷阱前累計的額外傷害(bonus damage)，1 是因為在跳開此陷阱時，額外傷害也不會計入其中，也就是該陷阱自己本身能避開的額外傷害。

avoid_dmgs從大至小進行排序，則前 k 項元素之合則是我們所能避開的最大傷害總計，也是貪婪之處。當減去此數後，我們需要再補正結果，因為記得我們一開始累計 ans 時，是沒有計算到額外傷害的，而當我們扣除 avoid_dmgs[0..k] 傷害時是有再扣除左側額外傷害(i + 1)。根據規則我們要再補上所有的額外傷害也就是程式碼的 len(可以理解為 -(left + 1) + all == right)。再 -= i 表示的意思是由於我們第 i + 1 次跳躍時，先前必定經歷過第 i 次跳躍，而跳躍當下是不用吃額外傷害的。

舉例來說，k 為 3 所有的陷阱基礎傷害為：

 8  2  5 15 11  2  8

全陷阱傷害總計 51 ，經過計算後，我們知道所有陷阱能分別能避開的傷害與左側額外傷害為：

 9  4  8 19 16  8 15

前 k 個應該躲開的陷阱傷害為：{15, 11, 8}，我們再回頭看未避開的陷阱：

 8  2  5  x  x  2  x
 8  2  5  x  x  4  x (with bonus)

此時如果 51 直接減去 50，必然會出現超減的狀況，只剩 1，很明顯與正確答案 19 有一大段差距，因此我們要進行補正，可以看下表弟一列，這表示我們在減去dmgs[i] + i + 1所造成的超減狀況。如果我們再依照 k 補上 len(相當於所有元素都+1)，就能避免超減的的狀況，

-3 -3 -3 -3 -2 -1 -1 (-avoid_dmgs[0..k])
 8  2  5  x  x  2  x (+0)
+3 +3 +3 +3 +3 +3 +3 (+len)
            +1 +2 +2

但其實仔細看會發現，我們補正傷害時，又會給原本應該要避掉的dmgs[i] + i + 1的 +1 給補回來，因此正確的形式其實是：

-3 -3 -3 -3 -2 -1 -1 (-avoid_dmgs[0..k])
 8  2  5  x  x  2  x (+0)
+3 +3 +3 +3 +3 +3 +3 (+len)
            +1 +2 +2
         -0 -1    -2