[解题纪录] 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;    }}