| WXYZ 的个人资料WXYZ的异人馆照片日志列表 |  工具  帮助 |
|
9月11日 PKU3059 -- Rummikub 本来只想上空间来听听《遇见我》的，的确是首好歌，百听不厌。突然觉得一边听歌一边写日志也不错啊，况且最近需要转换一下心情，并且要为空间增添些文字，再加上早几天有人鼓励，我还是写篇吧。说到心情，还是写篇解报告好了。
这是第二次写，PKU3059 -- Rummikub，这题目的大概意思是在平面上有4行100列格子，每列格子中的4个格子的分值就是这个格子的列号，分别从1到100，这些格子可以以两种方式消去：run和group。一个run就是同行的三个或以上的连续格子，一个group就是同一列中的三个（可以不连续）或四个格子。当格子组成run或group，那么所在run或group的格子就能全部消去，而消去所得的分值就是这些格子的分值之和。现在问题就是给定这400个格子中可以消去的格子，问你最多可以得多少分。
相信大多数人一看见这题，第一反应肯定是DP，但无奈于一个run可能很长，以致DP状态无法表示。我半年前也是这么想的。在半年后的今天，我重新看这道题，就发现一个问题了。一个run的长度大于等于6是没有意义的，因为这个run必定能拆成两个长度较小的run，也即是说，可以限定run的长度为3至5，这样当然就可以用状态压缩DP了，每一列为一层，每层状态数为2^(4*4)，这里底数2当然表示这个格能不能取了，而其中一个4表示4列，另一个4表示这行后面的4行，这样总状态数为100*2^16，这样的复杂度写好点当然可以过了。
想好状态后，剩下的只有状态转移了。我觉得这样的状态转移写得还是比较麻烦的，因为在这列中run可能有12种，group有5种，然后再组合一下，要写得简便还是的确不容易的，起码我的状态转移就写了120行以上，程序总长4K，过程还算快了，打完代码，编译，发现有错，原来是把memcpy写成strcpy了，一个替换改了，编译通过，试样例，过了，提交，Accepted，719ms，还真是一次过啊，省了不少麻烦，否则要调的话也不知道要花多少时间了。不过这题的运行时间也真长啊，时限才给1s，我想状态转移这里还是占了太多时间了，虽然初步写出来的带有少少优化的能过，但是相信这里还有很大的优化空间。
老实说，DP一直是我弱项，不是我不会用DP，而是看到题目不会往DP方面想，也不知道为什么会这样的。唉，弱啊弱啊弱。 |
|
|
