Skip to content

“彩球游戏”题解

郑重声明:本人并不自认为“会”此题,只是AC了,说说自己程序的思路而已。

原题:http://hi.baidu.com/astar/blog/item/fe22ab18c3c54b0635fa4192.htm

首先要对输入的数据进行预处理,按照“有连续的X个颜色为Y的小球”的格式,将连续的同色小球一起考虑。s[i]表示第i组小球的数量,type[i]表示第i组小球的类型。注意,所有连续的大于等于M个小球,都可以等价地当作M-1个小球来处理。

设计状态为v[i,j,k1,k2],表示第i组小球到第j组小球的左边多了k1个与s[i]同色的小球右边多了k2个与s[j]同色的小球时被完全消去的最小代价。平凡的状态包括:i>j时,状态的值为0;s[i]+k1>=M时,状态的值为v[i+1,j,0,k2];s[j]+k2>=M时,状态的值为v[i,j-1,k1,0];i==j时,状态的值为M-(s[i]+k1)。

对于非平凡的状态,只需要考虑最左边的一组小球或最右边的一组小球如何处理。以左边的这组小球为例,可取的策略有两种:使用M-(s[i]+k1)个小球将它们单独消去;设s[i]与s[x]同色,在[i+1..x-1]这个序列被先行消除后,将这组小球与s[x]合并后再消除。右边的小球也可以同样定义这两种策略。还有一种策略就是,当s[i]与s[j]同色时,将[i+1..j-1]这个序列先行消除,再将s[i]、s[j]以及k1+k2个小球同时消除。状态转移方程如下:

v[i,j,k1,k2]=min{
M-(s[i]+k2) + v[i+1,j,0,k2];
M-(s[j]+k2)+v[i,j-1,k1,0];
v[i+1,x,0,0]+v[x,j,s[i]+k1,k2] (if type[x]=type[i]);
v[i,x,k1,s[j]+k2]+v[x+1,j-1,0,0] (if type[x]=type[j]);
v[i+1,j-1,0,0] (if type[i]=type[j]&&s[i]+s[j]+k1+k2>=M);
v[i+1,j-1,0,0]+(M-(s[i]+s[j]+k1+k2)) (if type[i]=type[j]&&s[i]+s[j]+k1+k2<M);
}(i<x<j)

很麻烦吧……我也觉得很麻烦。 如果谁能简化一下那真是太好了。

这样的话,一共有O(N^2*M^2)个 状态,每组状态的转移需要O(N)的时间,总复杂度是O(N^3*M^2),不就严重TLE了么……话是这么说,也许这道题就能告诉我们Big O这种关于复杂度上界的分析有时是会不靠谱的。

具体实现时一定要采用自顶向下的DP实现,也就是所谓的记忆化搜索了。这时你会发现,实际需要计算出来的状态只占总状态数的一小部分。我对这题的4320个数据做了简单的统计,需要计算的非平凡状态的数量平均为2057.766个,其中此数量为0~1000的有2244个,1001~5000的有1541个,5001~10000的有393个, 10001~20000的有139个,20000以上的只有3个,最多的需要计算26621个状态。

我想这个题应该可以得到一个比O(N^2*M^2)更好的需要计算的非平凡状态数的上界,可本人算法分析的能力有限,希望有高人能够在这一点上指教一二。

最后说一下空间问题,如果开一个200x200x20x20的四维数组的话似乎太浪费空间了,另外,由于“内存分页”等我也不太理解的原因,程序的空间用量对实际运行时间(并非“用户时间”或CPU时间)是有影响的。我采用的方法是每次动态分配一个N*N*M*M的一维数组,用来模拟四维数组。例如状态v[i,j,k1,k2]在这个数组中的下标就应该是((i*N+j)*M+k1)*M+k2。当然,也可以将它理解成一种没有冲突的hash——将取值有限制的四元组映射为一个整数。对于本题的数据来说,我的程序最多时用了4128KB的空间。

于是,这道题的4320个数据就被比较完美的解决了。注意我并不是说这道题被完美的解决了,因为算法的理论复杂度仍然很高,不能保证无法设计出达到理论复杂度上界的数据。

欢迎批评指正。

zuma.rar 这是我做的cena评测包,内有我的程序,数据由陈启峰提供,共10组输入输出文件,每个输入文件中含432组数据。

5 Comments

  1. Yakizz wrote:

    这家伙以后可以进国防部了……

    Monday, May 28, 2007 at 22:11 | Permalink
  2. horace wrote:

    居然搬家了。

    Tuesday, May 29, 2007 at 23:03 | Permalink
  3. 西木 wrote:

    我给你发邮件了,查收。

    Thursday, May 31, 2007 at 18:26 | Permalink
  4. tianyi wrote:

    to 西木:
    received and replied

    Thursday, May 31, 2007 at 22:00 | Permalink
  5. 西木 wrote:

    and replied again :P

    Thursday, May 31, 2007 at 22:23 | Permalink

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*