題目

題目大意

Alice跟Bob要在一個矩陣上玩遊戲，這個矩陣有2個rows、m個columns，矩陣上的每一格有數個硬幣。

一開始，Alice跟Bob都站在(1, 1)，他們打算要走到(2, m)

+-----+-----+-----+-----+-----+-----+-----+
|(1,1)|     |     |     |     |     |     |
+-----+-----+-----+-----+-----+-----+-----+
|     |     |     |     |     |     |(2,m)|
+-----+-----+-----+-----+-----+-----+-----+

合法的移動方式：

• 往右走
• 往下走

Alice先走到目的，並且拿走所經過格子的所有金幣
Bob第二個出發，同樣也拿走所經過格子的所有金幣（請記得有些金幣已經被Alice拿走了）

Alice希望Bob收集到愈少金幣愈好
Bob希望Bob收集到愈多金幣愈好

如果兩人都走出自己的最佳路線，Bob最後會收集到多少金幣？

思路

這題要自己嘗試摹擬一下遊戲狀況，摹擬過後答案就容易出來了

先假設遊戲開始前矩陣長這樣(x代表數個金幣)：

+-----+-----+-----+-----+-----+-----+-----+
|  x  |  x  |  x  |  x  |  x  |  x  |  x  |
+-----+-----+-----+-----+-----+-----+-----+
|  x  |  x  |  x  |  x  |  x  |  x  |  x  |
+-----+-----+-----+-----+-----+-----+-----+

Alice走了某個路線後，矩陣長這樣：

+-----+-----+-----+-----+-----+-----+-----+
|  0  |  0  |  0  |  0  |  x  |  x  |  x  |
+-----+-----+-----+-----+-----+-----+-----+
|  x  |  x  |  x  |  0  |  0  |  0  |  0  |
+-----+-----+-----+-----+-----+-----+-----+

可以發現在這樣的狀況下，Bob一定會:

• 先往右走到底，再往下
• 先往下，再先往右走到底
  在這兩個可能中選最可以獲得最多金幣的方式

所以我們只要把Alice的所有可能路線的情況下，Bob的金幣數量求出，就可以得到答案了

程式碼

// https://codeforces.com/contest/1555/problem/C
#include <iostream>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t--) {
        int m;
        cin >> m;
        int a[2][m];

        for (int i = 0; i < m; i++)
            cin >> a[0][i];
        for (int i = 0; i < m; i++)
            cin >> a[1][i];
        
        int downIndexA, scoreMin, score0, score1;
        downIndexA = 0;
        score1 = 0;
        score0 = 0;
        for (int i = 1; i < m; i++)
            score0 += a[0][i];
        scoreMin = max(score0, score1);

        for (downIndexA = 1; downIndexA < m; downIndexA++) {
            score0 -= a[0][downIndexA];
            score1 += a[1][downIndexA-1];
            scoreMin = min(scoreMin, max(score0, score1));
        }

        cout << scoreMin << endl;
    }
}