P1199 NOIP2010 普及组 三国游戏

P1199 NOIP2010 普及组 三国游戏

P1199 [NOIP2010 普及组] 三国游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这题虽然是有博弈论的标签，但是完全没必要，直接贪心即可。

下面一个武将的最大默契值称为第一默契值，次大为第二，以此类推。

如何最大默契值

根据题意，通过观察规律，你会发现，对于任意一个武将，它第二默契值你一定可以选上（因为第一次，电脑只会封住最大的那个，第二大的你就可以选上），那么你可以把最大的第二默契值选上。

这时候你会发现，电脑所封住的默契值，第一种是一个武将第一默契，第二种是一个比其他武将第一默契值还大的一个非第一默契值。而你所选的是最大的第二默契值，也是最大的非第一默契值，这肯定比第二种大，而如果没有第二种，因为第一种的限制，所有武将的第一默契你肯定选不上，最多选上第二默契。因此，选最大第二默契一定是最优选法。

能否必胜

对于电脑它只注意封默契，我可以随便选，但我选不上的它一定选不上，而我选上了我能选上最大的，它能选最大的就一定比我小。从另一个方面说，只注意封住默契，怎么可能比我专门选大的还大呢？如果不能必赢，这游戏有什么意义呢？因此一定可以胜利。

代码就要好写多了。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

int g[N][N];
int n, m;
int maxv, cnt;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = i + 1; j <= n; j ++ )
            cin >> g[i][j], g[j][i] = g[i][j];
        sort(g[i] + 1, g[i] + n + 1);
        reverse(g[i] + 1, g[i] + n + 1);
        maxv = max(maxv, g[i][2]);
    }
    cout << 1 << endl << maxv << endl;
    
    return 0;
}