[计算机]《新手的dota》解题报告

《[计算机]《新手的dota》解题报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、作者声明：当动态规划维数进一步增大或不定时，标准解答方法为最大流。新手的DOTABysx349[题目背景]DOTA是DefenseoftheAncients的缩写，是一个基于魔兽争霸的多人实时对战自定义地图，可以支持10个人同时连线游戏。DOTA以对立的两个小队展开对战，最多为5v5。每个玩家仅需要选择一个英雄，并通过控制该英雄来摧毁对方小队所守护的主要建筑（远古遗迹），以取得最终胜利。[题目描述]A君是暴雪公司的忠实FANS，也算是个war3的老手了，自从接触到了DOTA之后，感觉这更适合自己这样的微操狂人。于是，A君拉上了四个死党，也开始接触DOTA

2、了。既然是新手，首先就是要熟悉一下界面、英雄……等等。在经过一番恶补之后，A君率先出师，随后大家也纷纷学成。接下来，就要进行实战演练拉。五个新手立刻进入游戏，很不幸，他们下载了一张非AI版地图（这也是很多新手遇到的尴尬）。作为这个小团队的领导者，A君决定，先来一局5V0（五英雄对零英雄），进行一次试练。在整张地图上不仅有对方一拨拨的小兵，还有很多的野外中立兵。五个新手经过讨论，决定分别找出一条从自己老家（坐标为1，1）通往敌方老家（坐标为N，N）的路，一波RUSH直接结束战斗。显然，敌方老家是很难打得（尤其是有强大的通灵塔守护）。所以，他们希望英雄在路上

3、能够尽可能多地MF，尽可能的练到更高等级。假设我们已经知道了整张地图的大小N以及所有兵力配置（只是开了一下全地图可见……），五个英雄依次出发，每一次向右或向下移动一格，直到到达敌方的远古遗迹。如果某个地点已经被到达过，那么到达这一地点的英雄必然会杀死所有的处于该地点的单位，而且不再刷新。当然，由于我们的英雄等级都不会太高，所以每一格中的单位数量也不会超过10000个，不然的话……A君想知道，他们这一波RUSH最多能解决掉多少单位？[输入格式]第一行是一个整数N，表示整张地图（正方形）的边长。第二到N+1行，每行有N个数字，表示地图中每个点的兵力配置。[输

4、出格式]输出一个整数S，表示最多能解决掉的单位。[输入样例1]3123234345[输出样例1]27//所有的单位都被解决了[输入样例2]6256791648684169848168416987463841031[输出样例2]181//除了右上角的一个单位以外全部解决了[数据范围]对于50%的数据，有0

5、且规则仍旧为同一点不重复取。显然，我们可以考虑这样的做法：枚举两个人所走的坐标的X，Y值来进行动态规划。由于要枚举每一个点的坐标，所以所需的空间复杂度达到O（n4），而时间复杂度也要达到O（n4）。由于在原题中的数据范围较小，因此虽然复杂度很高，但是还是能够通过的。但是直接套用到这道题上，现仍然是不行的。在这一题中，要考虑5个点的坐标的X，Y的值，因此数组下标将会有10个，空间复杂度与时间复杂度将要高达O（n10），无论在空间还是时间上都是令人无法忍受的。我们考虑方格取数中可以使用的另一种方法。考虑每个英雄走到第K步时格子的坐标：KXYX+Y111221

6、232133134……………………可以看出，X+Y=K+1。这是不是一条普遍规律呢？我们再来模拟一下某一条路径。S1（1，1）↓S2（2，1）→S3（2，2）→S4（2，3）↓S5（3，3）→S6（3，4）↓S7（4，4）↓S8（5，4）→S9（5，5）因为起始位置固定为（1，1），而K为1，所以此时满足X+Y=K+1。此后的每一步，X或Y的值中的一个加1，并且K加1，相当于等式两边都加1，等式依旧成立。因此，我们只要考虑每个英雄所在的坐标的X值，就可以根据当前步数K得到Y值。这时，参数的个数就降为N+1个，这时的空间复杂度和时间复杂度就降到O（n6）了

7、。由于n最大为10，所以基本上空间和时间方面没有问题。为了避免数组越界，同时方便计算，我们沿对角线将整张地图分成两部分：灰色部分的K值由1变化到N，相应的各英雄坐标的X值有可能是1~K中的任何一个。白色部分的K值由N+1变化到2*N-1，相应的各英雄坐标的X值有可能是K-N+1~N中的任何一个。将动态规划分成这两个部分，除了每个部分中各变量变化范围不同外，决策没有变化，所以不影响最后结果。接下来考虑决策选择。显然，每一步英雄只有可能从其上方的格子或左边的格子走过来。从上方的格子走过来，则X值不变（Y值同时要加一，但是我们Y可以根据K和X求出，不用考虑）；

8、从右边的格子走过来，则X值较前一个状态加一。由于我们有五个英雄，每个英雄都有这两