荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: selahx (宿醉未散，早梦半醒), 信区: ACMICPC
标 题: Re: A GAME
发信站: 荔园晨风BBS站 (2004年10月08日16:22:40 星期五), 站内信件
数学策略的想法：
【例5】N个正整数横向排列，两人轮流从中取数，每次只能取走最左端或者最右端的数，
所取数的数值表示这个人这次的得分。所有数都取完时，每个人所得分数之和为这个人的
最后得分，最后得分多的人获胜。如果两人得分相同，则规定首先取数的人获胜。【附录8
】
如果游戏开始N为偶数，则对首先取数的人来说存在一种必胜的策略。请编一个程序，作为
首先取数的人，寻找一种必胜的策略和计算机玩这个游戏。
我们不妨将题目做一下处理，把要处理的对象染上不同的颜色，从而可以区分它们，这样
才能够看出其中的一些隐蔽的本质。将要拿的数字染成不同的颜色，像这样：
4 7 2 9 5 2
图10
实际上，先拿的人有权拿走所有自己想要颜色的数字。也就是说，先拿的人想拿走深色的4
，2，5这三个数，就可以拿走，具体是这样的：
（1） 拿走4，对手只能拿7或9，而它们都是浅色的；
（2） 无论对手怎样拿，都有一个（也仅有一个）深色数字可拿，那么就将它拿走
；
（3） 对手仍然只能选择浅色数字；
（4） …
这样拿下去，只要先拿的人每次都选择深色数拿，必定能够将所有深色数拿走。
这意味着什么？这意味着先拿的人只要选择两种颜色中数字总和较大的那组数，就可以保
证胜利了。
【 在 selahx ( 宿醉未散，早梦半醒) 的大作中提
到: 】: 一看题目就想起博弈了，印象中是可以数学策略做的，不过数学策略好像不能满足
: 最优策略，于是就用dp，就做出来了~还是想最优子结构想了半天~sign~
: 【 在 selahx (宿醉未散，早梦半醒) 的大作中提到: 】
: : A Game
: : IOI'96 - Day 1
: : Consider the following two-player game played with a sequence of N positive
: : integers (2 <= N <= 100) laid onto a game board. Player 1 starts the game.
: : The players move alternately by selecting a number from either the left or
: : the right end of the sequence. That number is then deleted from the board,
: : and its value is added to the score of the player who selected it. A player
: .................（以下省略）
--
oノ\ ╲╱ ;-\ o╲ ﹀--ˊ 当太阳下山后 我就变成恶魔
/0 ヽ " / 0; |0 ◣
( ╲ / \o 0\ `~ `` █◣~~ ~~ 哼哼
o\ | .\ o╲o 0\ ~~ ██◣ ~~ ~ 哈哈
|0 / / 0\ o╲ `~ ~~ ◥▄▄▄▄◤ ~
/ \ ~~~~~ ~~ ~~ ~~ ~~
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.1.55]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店