AcWing 1388. 游戏（博弈论 + 区间DP）    原题链接    简单

作者： 作者的头像   比比鼠 ,  2024-03-30 08:37:03 ,  所有人可见 ,  阅读 161

2


C++ 代码

#include <iostream>

using namespace std;

const int N = 110;

int w[N];
int f[N][N]; //在先手的情况下，在i到j的区间，先手选手和后手的最大分差
int n, sum;

//  ∵
//  x + y = sum
//  x - y = f[0][n - 1]
//  ∴
//  x = (sum + f[0][n - 1]) / 2
//  y = (sum - f[0][n - 1]) / 2

int main()
{
    cin >> n;
    for(int i = 0 ; i < n ; i ++)
    {
        cin >> w[i];
        sum += w[i];
    }

    for(int len = 1 ; len <= n ; len ++)
        for(int l = 0 ; l + len - 1 < n ; l ++)
        {
            int r = l + len - 1;
            f[l][r] = max(w[l] - f[l + 1][r], w[r] - f[l][r - 1]);
        }

    cout << (sum + f[0][n - 1]) / 2 << " " << (sum - f[0][n - 1]) / 2 << endl;

    return 0;
}

5 评论

用户头像
h闵   9个月前         踩      回复

为啥这个可以成立啊，y总说f[i][j]是从第i个数到第j个数的先手值减去后手值的最大值，为什么右边这个就可以成立啊？这个部分也挺不理解。f[i][j] = max(w[i] - f[i + 1][j],w[j] - f[i][j - 1]);

用户头像
比比鼠   9个月前         踩      回复

w[i] - f[i + 1][j]的意思是说：我这次取i，那此时我的总值减去对手总值的差（f[i][j]）就是上一局我减对手的差值+w[i]，而f[i + 1][j]表示的是对手减我的差，因此 （取相反数）‘+’变‘ - ’，便是max(w[i] - f[i + 1][j],w[j] - f[i][j - 1])表示取最左边和最右边的较大值

用户头像
h闵   9个月前         踩      回复

为什么不是7 + 9 + 5 - 4 - 2 - 2呢，然后一边是21，一边是8，根本理解不了啊，这是什么意思啊？

用户头像
比比鼠   9个月前      1    踩      回复

你的意思应该是，按照贪心的思路每次选左右边界处最大的值，但这不是最优方案，比如样例：如果我第一次选4，那么对手就可以选7，而我下一轮只能选到2，但如果我第一次选的是2，那么下一轮我就可以选7。注意题目里说：“如果双方都采取最优策略进行游戏”，所以我和对手每次选都是站在全局的角度选最优解的。

用户头像
h闵   9个月前    回复了 比比鼠 的评论         踩      回复

嗯，这个我知道了，但是感觉这个f[i][j] = max(w[i] - f[i + 1][j],w[j] - f[i][j - 1]);也挺难懂的，为什么这个就是最大值呢？
for(int len = 1;len <= n;len)
{
for(int i = 0;i + len - 1 < n;i)
{
int j = i + len - 1;
// cout << w[i] - f[i + 1][j] << ‘ ‘ << w[j] - f[i][j - 1] << endl;
f[i][j] = max(w[i] - f[i + 1][j],w[j] - f[i][j - 1]); //这个就是视为是各个数之间的差值的叠加的，取一个最大值。
// f[i][j] = max(w[i] - f[i + 1][j],w[j] - f[i][j - 1]); //这个就是视为是各个数之间的差值的叠加的，取一个最大值。
}
}