自动搬运

查看原文

来自洛谷，原作者为

	orangebird 退役OIer

搬运于2025-08-24 21:52:48，当前版本为作者最后更新于2017-06-08 22:23:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

第0个测试点

送分，注意开局C连续行动两次。

第1个测试点

可以推出公式为2^(nm+2)-4，用快速幂处理即可。

第2个测试点

n,m只有2，手玩即可

第3个测试点

经典2048规则。

盘面达到

13W 64K 32K 16K

8K 4K 2K 1K

512 256 128 64

32 16 8 4

时和最大。

最大分数:除了16个合成最大数的关键

时刻必须出4以外，其他均出2，可以得到3632164-16*4=3932100分。

和最大时的最小得分:每一步都出4，可以得到3670024分。

第4个测试点

非常裸的贪心，全部放在一列即可，最好写程序来模拟一下，手动计算分数太麻烦。

第5个测试点

动态规划。

dfs预处理每一列第一行的数字为x，放i个2，j个4可以得到的最大价值val(x,i,j)。

用dp[i][j][k]表示当前已经完成了前i行,还剩j个2,k个4时的最大得分。

可以得到递推式dp[i][j][k]=max(dp[i-1][j'][k']+val(i,j'-j,k'-k))

初始状态所有dp值均为0

最终答案是max(dp[m][i][j])

第6个测试点

与第2个测试点相同，只是棋盘大小变为3*3。

虽然只增大了一点范围但是绝对不可手玩。

双方是对抗关系，因此选择max-min搜索法,每个格子的数字有11种可能，每个局面可以轮到玩家M或C，因此状态是11^9*2。

由于2048游戏的特点，一个状态可以由不同状态转移而来，因此使用记忆化搜索可以大大节省时间。

第7个测试点

注意分数不能算作状态的一部分，否则状态数量会爆炸。

正确的做法应该是保存当前节点向下可以得多少分，然后用与第6个测试点相同的方法搜索即可。

如果记忆化的话就不能用alpha-beta剪枝，因为被beta截断后记忆化存下的结果可能是错误的。

如果仔细分析会发现一个问题，如果直接存储状态，需要的内存超过8GB，一般机器难以接受。

我们记忆化搜索可以只存move节点的结果，这样最坏情况下，时间会增加4倍。因为在move节点的4个移动方向得不到create的答案，只能再往下搜索。

但不是所有节点4个移动方向都是有效的，实际看来时间只增加了一倍，空间可以优化到1/2。

第8个测试点

这里玩家C不再和玩家M对抗，因此改变搜索策略，在玩家C行动的节点取所有子节点达到目标数字的概率和走到该子节点概率相乘，求和的结果。

因为最高只要求算出达到512的概率，所以实际搜索的节点数会大大减少，再加上只对部分节点进行记忆化的优化，空间不会爆。

第9个测试点

与第8个测试点搜索方法类似，但需要搜完全部的节点，对内存要求更高。

下面祭出终极优化，同时优化时间和空间:

一个局面旋转和翻转可以变换成8个等价局面，我们只需要存字典序最小的那个就行。