题解 P3798 【辉夜姬的十道难题】

orangebird · 2017-06-08 22:23:01 · 题解

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

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

n,m只有2，手玩即可

经典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分。

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

动态规划。

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])

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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