731-E. Funny Game

2021-03-16 01:06:43 +0800 CST Tags: game-theory, prefix-sum

出處：https://codeforces.com/contest/731/problem/E
提交：https://codeforces.com/contest/731/submission/107249075

問題：給定 $n\in[2,200000]$ 個介於 $[-10000,10000]$ 的整數，每次玩家可以吃掉從左邊往右數來至少 2 個、至多全部的數字，並補回一個等值於這次吃掉的數字總和的數字到數列的最左邊，而這個加總可以納入這位玩家的積分。遊戲進行到僅剩一個數字的時候停止，假設每一步玩家都採取對自己有利的最佳策略，也就是最大化當下自己減去對方未來積分的差距，那麼請問這場遊戲結束之後先手積分減去後手積分的差值？

解法：這題是很典型的遊戲理論，必須使用 DP 解決。注意到分析的時候我們用「融合前面 i 個數字」去取代掉「吃掉前面 i 個數字和補回一個數字」的這個動作，因此這些數字的 index 是不會改變的。由於每次遊戲的狀態只跟最前面已經有幾個數字被融合為一體有關，所以我可以讓 dp[i] 去記錄當最前面 i 個數字被融為一體的時候「此時的先手」積分減去「此時的後手」積分的差值。當 $i\in[1,n-1]$ 個數字已經被融合，這一輪的玩家就必須至少再次融合前 i+1 個、至多全部的數字，至於先手究竟要選擇融合幾個數字？為了要採取對自己有利的最佳策略，他/她會選擇「最大化」(此次融合得到的分數) 減去 (下一回合的先手積分減去後手積分的差值)，於是我們可以寫出遞迴式：$\text{dp}[i] = \max \{\text{sum}[j]-\text{dp}[j]\ |\ i<j<=n\}\text{ for }i\in[1,n-1]$ 其中 dp[n]=0、sum[j] 代表前面 j 個數字的和。其中 sum[1:n] 可以用 prefix sum 技巧在線性時間算出，另外 dp 陣列其實也可以倒過來算，因為 $\text{dp}[i] = \max \{\text{sum}[i+1]-\text{dp}[i+1],\ \text{dp}[i+1]\}\text{ for}$$i\in[1,n-2]$、但是要記得 $\text{dp}[n-1] = \text{sum}[n]$ [1]，這樣的話就也是線性時間。

附註：
[1] 想想看為什麼 dp[n-1] 不可以寫成 $\max \{\text{sum}[n]-\text{dp}[n],\ \text{dp}[n]\}$？

實作：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


#include <bits/stdc++.h>
using namespace std;

/* Given arr[1:n] where n<=200000, we define:
   sum[i] = sum {arr[j] | 1<=j<=i} for 1<=i<=n, and let
   dp[i] be the best difference that the first player can achieve
      if arr[1:i] is merged to be one element beforehand (for 0<=i<=n-1), and
      dp[n] = 0 since the game ends if only one element is present in the array, then:
   dp[i] = max {sum[j]-dp[j] | i<j<=n} for 1<=i<=n-1. Note that it can also be reduced to:
         = (1) max {sum[i+1]-dp[i+1], dp[i+1]} for 1<=i<=n-2, and
         = (2) sum[n] for i==n-1,
   so the array "dp" can be calculated in reversed order smoothly. In this way actually
   we don't need the value of dp[n].
*/

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
    int n, dp, sum[200001]={0};
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> sum[i];
        sum[i] += sum[i-1];
    }
    dp = sum[n]; // dp[n-1] = ...
    for(int i=n-2; i>=1; i--)
        dp = max(sum[i+1] - dp, dp); // dp[i] = ...
    cout << dp << endl;
    return 0;
}

結果： Example image