【NOIP2010】洛谷1199 三国游戏

2023-11-07 20:32

本文主要是介绍【NOIP2010】洛谷1199 三国游戏,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

小涵很喜欢电脑游戏,这些天他正在玩一个叫做《三国》的游戏。

在游戏中,小涵和计算机各执一方,组建各自的军队进行对战。游戏中共有 N 位武将(N为偶数且不小于
4),任意两个武将之间有一个“默契值”,表示若此两位武将作为一对组合作战时,该组合的威力有多大。游戏开始前,所有武将都是自由的(称为自由武将,一旦某个自由武将被选中作为某方军队的一员,那么他就不再是自由武将了),换句话说,所谓的自由武将不属于任何一方。

游戏开始,小涵和计算机要从自由武将中挑选武将组成自己的军队,规则如下:小涵先从自由武将中选出一个加入自己的军队,然后计算机也从自由武将中选出一个加入计算机方的军队。接下来一直按照“小涵→计算机→小涵→……”的顺序选择武将,直到所有的武将被双方均分完。然后,程序自动从双方军队中各挑出一对默契值最高

的武将组合代表自己的军队进行二对二比武,拥有更高默契值的一对武将组合获胜,表示两军交战,拥有获胜武将组合的一方获胜。

已知计算机一方选择武将的原则是尽量破坏对手下一步将形成的最强组合,它采取的具体策略如下:任何时刻,轮到计算机挑选时,它会尝试将对手军队中的每个武将与当前每个自由武将进行一一配对,找出所有配对中默契值最高的那对武将组合,并将该组合中的自由武将选入自己的军队。
下面举例说明计算机的选将策略,例如,游戏中一共有 6 个武将,他们相互之间的默契值如下表所示:

双方选将过程如下所示:

小涵想知道,如果计算机在一局游戏中始终坚持上面这个策略,那么自己有没有可能必

胜?如果有,在所有可能的胜利结局中,自己那对用于比武的武将组合的默契值最大是多

少?
假设整个游戏过程中,对战双方任何时候均能看到自由武将队中的武将和对方军队的武将。为了简化问题,保证对于不同的武将组合,其默契值均不相同。

输入输出格式 输入格式:

输入文件名为 sanguo.in,共 N 行。

第一行为一个偶数 N,表示武将的个数。

第 2 行到第 N 行里,第(i+1)行有(Ni)个非负整数,每两个数之间用一个空格隔

开,表示 i 号武将和 i+1,i+2,……,N 号武将之间的默契值(0≤默契值≤1,000,000,000)。

输出格式:

输出文件 sanguo.out 共 1 或 2 行。

若对于给定的游戏输入,存在可以让小涵获胜的选将顺序,则输出 1,并另起一行输出

所有获胜的情况中,小涵最终选出的武将组合的最大默契值。

人一定不能取到对于某个武将来说最大的,因为选了这个武将之后电脑一定会把这一对拆散。但是,在这之后人就可以选第二大的了。所以对于每个武将的第二大值的最大值就是答案。

#include<iostream>
#include<algorithm>
using namespace std;
int a[510][510];
int main()
{int i,j,n,ans=0;cin>>n;for (i=1;i<=n;i++)for (j=i+1;j<=n;j++){cin>>a[i][j];a[j][i]=a[i][j];}for (i=1;i<=n;i++){sort(a[i]+1,a[i]+n+1);ans=max(ans,a[i][n-1]);}cout<<"1"<<endl<<ans<<endl;
}

这篇关于【NOIP2010】洛谷1199 三国游戏的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/366125

相关文章

三国地理揭秘:为何北伐之路如此艰难,为何诸葛亮无法攻克陇右小城?

俗话说:天时不如地利,不是随便说说,诸葛亮六出祁山,连关中陇右的几座小城都攻不下来,行军山高路险,无法携带和建造攻城器械,是最难的,所以在汉中,无论从哪一方进攻,防守方都是一夫当关,万夫莫开;再加上千里运粮,根本不需要打,司马懿只需要坚守城池拼消耗就能不战而屈人之兵。 另一边,洛阳的虎牢关,一旦突破,洛阳就无险可守,这样的进军路线,才是顺势而为的用兵之道。 读历史的时候我们常常看到某一方势

国产游戏崛起:技术革新与文化自信的双重推动

近年来,国产游戏行业发展迅猛,技术水平和作品质量均得到了显著提升。特别是以《黑神话:悟空》为代表的一系列优秀作品,成功打破了过去中国游戏市场以手游和网游为主的局限,向全球玩家展示了中国在单机游戏领域的实力与潜力。随着中国开发者在画面渲染、物理引擎、AI 技术和服务器架构等方面取得了显著进展,国产游戏正逐步赢得国际市场的认可。然而,面对全球游戏行业的激烈竞争,国产游戏技术依然面临诸多挑战,未来的

火柴游戏java版

代码 /*** 火柴游戏* <p>* <li>有24根火柴</li>* <li>组成 A + B = C 等式</li>* <li>总共有多少种适合方式?</li>* <br>* <h>分析:</h>* <li>除去"+"、"="四根,最多可用火柴根数20根。</li>* <li>全部用两根组合成"1",最大数值为1111。使用枚举法,A和B范围在0~1111,C为A+B。判断</li>** @

国产游戏行业的崛起与挑战:技术创新引领未来

国产游戏行业的崛起与挑战:技术创新引领未来 近年来,国产游戏行业蓬勃发展,技术水平不断提升,许多优秀作品在国际市场上崭露头角。从画面渲染到物理引擎,从AI技术到服务器架构,国产游戏已实现质的飞跃。然而,面对全球游戏市场的激烈竞争,国产游戏技术仍然面临诸多挑战。本文将探讨这些挑战,并展望未来的机遇,深入分析IT技术的创新将如何推动行业发展。 国产游戏技术现状 国产游戏在画面渲染、物理引擎、AI

第四次北漂----挣个独立游戏的素材钱

第四次北漂,在智联招聘上,有个小公司主动和我联系。面试了下,决定入职了,osg/osgearth的。月薪两万一。 大跌眼镜的是,我入职后,第一天的工作内容就是接手他的工作,三天后他就离职了。 我之所以考虑入职,是因为 1,该公司有恒歌科技的freex平台源码,可以学学,对以前不懂的解解惑。 2,挣点素材钱,看看张亮002的视频,他用了6000多,在虚幻商城买的吸血鬼游戏相关的素材,可以玩两年。我

nyoj 1038 纸牌游戏

poj 的一道改编题,说是翻译题更恰当,因为只是小幅度改动。 一道模拟题,代码掌控能力比较好,思维逻辑清晰的话就能AC。 代码如下: #include<stdio.h>#include<string.h>#include<algorithm>using namespace std;struct node{char c[5];int rk;char da[5];int nu

如果出一个名叫白神话悟空的游戏

最近黑神话由于与原著不符引起了原著派的争议。 所以我在摸鱼的时候想到如果游科或者某个别的公司“痛改前非”不夹带私货完全复刻吴承恩百回版剧情制作一个“重走西游路”的游戏,会有一个什么样的销量?(设定为原著派已经多方渠道认证,此游戏的确没有夹带私货,绝大部分复刻了原著剧情) 游戏玩法我想了几类 超长线性有岔路蜈蚣形状地图,蜈蚣的腿部是探索区域和支线,重走西游路线,开篇就是开始取经前唐玄宗御弟cg

《黑暗之魂2:原罪学者》是什么类型的游戏 《黑暗之魂》可以在苹果Mac电脑上玩吗?

在宏大的世界观游戏中,《黑暗之魂2:原罪学者》脱颖而出,以其探索性和挑战性征服了全球玩家的心灵。下面我们来看看《黑暗之魂2:原罪学者》是什么类型的游戏,《黑暗之魂2:原罪学者》可以在苹果电脑玩吗的相关内容。 一、《黑暗之魂2:原罪学者》是什么类型的游戏 《黑暗之魂2:原罪学者》作为《黑暗之魂2》的增强版和重制版,是一款FromSoftware制作、BANDAI NAMCO和FromSoft

高精度计算(代码加解析,洛谷p1601,p1303)除法待更新

目录 高精度加法 高精度减法 高精度乘法 高精度加法 我们知道在c++语言中任何数据类型都有一定的表示范围。当两个被加数很大时,正常加法不能得到精确解。在小学,我们做加法都采用竖式方法。那么我们也只需要按照加法进位的方式就能得到最终解。 8 5 6+ 2 5 5-------1 1 1 1 加法进位: c[i] = a[i] + b[i];if(c[i] >=

简单取石子游戏~博弈

很坑爹的小游戏,至于怎么坑爹,嘎嘎~自己研究去吧~! #include<stdio.h>#include<windows.h>#include<iostream>#include<string.h>#include<time.h>using namespace std;void Loc(int x,int y);/*定位光标*/void Welcome(); /*创建欢迎界面*/