[解题纪录] Coin Rows

题目

题目大意

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;
    }
}