算法題 | 你能想出解法，讓你的基友少氪金嗎？

大家好，今天codeforces專題選擇的是一場education比賽的C題。

Education是codeforces的一種特殊賽事，它的主要作用是教育，也就是讓更多的人了解codeforces的比賽機制。是以education賽事的題會相對來說容易一些，更加适合新手。我選的這道題雖然是C題，但是難度并不高非常基礎。

連結：https://codeforces.com/contest/1418/problem/C

這題通過的人數有3600多，相比之前介紹的題算是比較少，但是題目難度其實更低一些。我們廢話不多說來看題目。

題意

這道題的題意也很有意思，背景也是遊戲。說是有一天你和你的基友一起在家打遊戲，這個遊戲一共有n個boss。這些boss的難度不同，有些boss簡單，有些boss困難。你的技術要比基友的好一些，你們兩人輪流打boss。

遊戲規定每次進行遊戲最少打1個boss，最多打兩個boss。由于你的實力更好，你可以戰勝所有的boss。但是你的基友比較菜，隻能打得過簡單的boss，如果碰上hard模式的boss就隻能氪金。基友的錢也是錢，你們希望在盡量少氪金的前提下把遊戲通關。現在已知所有boss的難易情況并且基友先開始遊戲，請問在最佳政策下，最少需要氪金多少次？

樣例

首先給定一個數字t，表示測試資料組數。對于每組資料，給定一個數字n，表示boss的數量。接着給定n個0或者1的整數，0表示boss是簡單模式，1表示是困難模式。要求傳回一個數字，即最少的氪金次數。其中

input: 
8
1 0 1 1 0 1 1 1

output:
2
           

基友先殺1和2兩個boss，氪金一次。

“我”殺3和4号boss

基友殺5号boss

“我”殺6和7号boss

基友擊殺8号boss，氪金一次，總共氪金兩次。

題解

這道題我們最先想到的可能就是貪心，比如我們可以想到一種貪心政策，就是每次基友殺怪的時候先殺1個，然後看第二個是0還是1，如果是0的則一起殺了，否則不殺留給“我”。

我們可以用之前介紹過的等價判斷法來判斷一下這個貪心政策可不可行，對于這道題而言，貪心的本質是讓氪金的次數最少。是以當基友的第二個怪是0的時候，殺和不殺對于目前的氪金次數來說是沒有影響的。但是對于後面的局面是會有影響的，并且可能會出現不同的結果。

比如我們可以找到一個例子10011，基友殺不殺第二個怪，直接影響後面的結果。如果基友殺了，那麼不論“我”怎麼選，基友都必須要至少再氪金一次。如果基友不殺，那麼“我”殺第二個怪，基友再殺第三個怪，最後兩個boss都交給“我”，那麼基友全局隻需要氪金一次。是以貪心算法不可行。

動态規劃

如果你熟悉動态規劃的話，那麼幾乎可以發現這是一道經典的動态規劃問題。對于每一個怪來說，它都有兩種狀态，分别是被基友殺或者是被“我”殺。我們用0和1來分别表示，0表示被基友殺，1表示被“我”殺。一共有n個怪，是以我們可以用一個n * 2的數組來記錄所有怪的狀态。

對于第i個怪而言，如果它是被“我”殺的，那麼它可以由基友殺了i-1或者是i-2個怪的狀态轉移得到。比如如果從基友殺了i-1轉移得到，說明“我”殺了i，否則說明“我”不僅殺了i，還殺了i-1。同理i被基友殺的情況也是一樣，是以這個狀态轉移方程就非常明顯了。

import sys

t = int(input())

for _ in range(t):
    n = int(input())
    arr = list(map(int, input().split(' ')))
    dp = [[sys.maxsize, sys.maxsize] for _ in range(n+2)]

    dp[0][1] = 0

    for i in range(1, n+1):
        if i > 1:
            # 如果i > 1，那麼說明可以殺兩個
            # 0表示基友殺怪的情況，基友可以殺1個從i-1轉移得到，也可以殺2個從i-2轉移得到
            # 需要加上氪金的次數
            dp[i][0] = min(dp[i-1][1] + arr[i-1], dp[i-2][1] + arr[i-2] + arr[i-1])
            # 我殺怪不用氪金，直接指派即可
            dp[i][1] = min(dp[i-1][0], dp[i-2][0])
        else:
            # i=1，那麼隻能殺一個
            dp[i][0] = dp[i-1][1] + arr[i-1]
            dp[i][1] = dp[i-1][0]

    print(min(dp[n][0], dp[n][1]))
           

這道題非常的基礎，可以說是動态規劃的基礎問題了。如果對動态規劃這個概念不是很熟悉的話，非常建議動手做一做，加深一下印象。

衷心祝願大家每天都有所收獲。如果還喜歡今天的内容的話，請來一個三連支援吧~（點贊、關注、轉發）

原文連結，求個關注

本文使用 mdnice 排版

- END -