#2245. 暗渡陈仓
暗渡陈仓
题目背景
示之以动,利其静而有主,“益动而巽”。
题目描述
小雨 和 浩然 正在玩一款游戏。游戏中有 个城市,从左到右编号从 ,编号为 的城市有 的资源。
- 小雨 一开始在城市 ,浩然 一开始在城市 。
- 游戏轮流进行,小雨 先操作,浩然 后操作。两人所在城市相邻时游戏结束。
- 假设 小雨 在城市 。轮到他操作时有两种操作方法:他可以选择可以走到城市 ;或者如果 浩然 不在城市 ,就可以绕过城市 ,暗渡走到 。
- 假设 浩然 在城市 。轮到他操作时有两种操作方法:他可以选择可以走到城市 ;或者如果 小雨 不在城市 ,就可以绕过城市 ,暗渡走到 。
- 游戏最终的评分为“小雨 走到的所有城市的资源值之和”减去“浩然 走到的所有城市的资源值之和”的数值。
- 小雨 的游戏目标为最大化最终评分,浩然 的目标为最小化最终评分。
假设两个人都足够聪明,请你输出最终评分会是多少。
输入格式
第一行为一个数 。
第二行为 个整数 。
输出格式
一个整数,即最终评分。
2
1 3
-2
游戏一开始就结束了。
4
2 2 2 2
2
显然如果第一轮 小雨 往右走一步,浩然 就也能往左走一步了,最终得分就是 。所以 小雨 第一轮就会暗渡到 ,会走过城市 ,浩然 会走过城市 。
4
2 6 2 2
4
- 比赛可能性 1:小雨 走过城市 ,浩然 会走过城市
- 比赛可能性 2:小雨 走过城市 ,浩然 会走过城市
显然 小雨 会把游戏引导到第二种结果中。
数据规模与约定
对于 的数据,,。
- 子任务 1(10 分):保证 。
- 子任务 2(20 分):保证 。
- 子任务 3(30 分):保证 。
- 子任务 4(40 分):没有特殊限制。
相关
在下列比赛中: