“彩球游戏”题解
Saturday, May 26th, 2007
郑重声明：本人并不自认为“会”此题，只是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)更好的需要计算的非平凡状态数的上界，可本人算法分析的能力有限，希望有高人能够在这一点上指教一二。
最后说一下空间问题，如果开一个200×200×20×20的四维数组的话似乎太浪费空间了，另外，由于“内存分页”等我也不太理解的原因，程序的空间用量对实际运行时间（并非“用户时间”或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组数据。
Tags: 彩球游戏, 百度之星
Related posts
百度之星复赛
AStar2007进复赛了