飞

一年以前还在高中搞信息学竞赛的时候就有了这道题，当时觉得一点思路都没有，感觉是没法解决的。后来看到discuss里面说压缩之类的也没大明白。

前几天想回过头来做点Ural上面的题，第一个就看到了这个，于是就想把他办掉。不过压缩算法是我从来没接触过的，查了一些资料，也找到了一些这方面的文章和论文。看了一下对信息论的那些东西没大搞明白。不过把LZ77压缩算法看懂了。昨天晚上就试着做了一下。结果弄了半天都没有过，总是Wrong Answer on Test 1。有点搞不懂是为什么，自己作的几个测试数据都没有问题。当时已经2点多了，就没在做。

今天起床后继续，发现当那一串字符的长度在20000左右的时候压缩的效果并不明显，甚至增大了体积。把dictionary和buffer的大小都调大了一些，结果压缩的好了，花的时间也长了，Time Limit Exceeded on Test 3。又研究了一下gzip对LZ77的那几个改进，看了看gzip的源码，稍微有点思路怎么弄了，不过到了该去学文化课的时间了，就没在去管他。并且觉的这些改进都有些麻烦，感觉思路很乱，有点想放弃了。

不过我还是有点不甘心，所以下午去图书馆的时候在路上一直想细节上怎么去继续优化，结果在回来的路上终于想明白了。于是从晚上11点多又开始做，经过改进后的算法在dictionary和buffer的大小不变的情况下，压缩率明显提高，不过碰到了一些小问题让我调试了好久。最终还是成功了，真是让我激动万分。可能是由于这个题目的难度所导致，也有可能是因为做了这么久才做出来，我感觉从来没有哪次做出一个题目或者编出一个程序而让我如此激动过。

顺便截了个图，贴上来庆祝一下。

2006-03-30 13:01:55 Accepted 0.008 Minimum C++ 103 - Stacking Boxes

这道题不是很难，是一个典型的动态规划。
首先，我们先要找到一个高效的算法来判断一个盒子是不是能放在另一个盒子里，这很简单，我们可以推出这样一个结论

如果一个盒子能放在另一个盒子里，当且仅当把这两个盒子的坐标排序后，第一个盒子的每一维都严格小于第二个盒子的每一维。

来证明一下。如果把这两个盒子的坐标排序后，第一个盒子

(a1,a2,...,an)，其中a1<a2<...<an

的每一维都严格小于第二个盒子

(b1,b2,...,bn)，其中b1<b2<..<bn

的每一维，那么跟据题意，第一个盒子可以放到第二个盒子里。反过来，如果第一个盒子可以放到第二个盒子里，跟据题意，则第一个盒子的坐标存在一种排列

(ak1,ak2,ak3,...,akn)

满足：

ak1<b1
ak2<b2
...
akn<bn

如果ak1<ak2<...<akn，则符合结论。如果存在一个aki>akj(其中i<j)，

因为akj<aki,aki<bi,所以akj<bi
因为aki<bi,bi<bj,所以aki<bj

可见将它们互换，同样满足条件。所以可以通过这种互换，来达到a1<b1,a2<b2,...,an<bn，所以结论成立。

这样以后问题就简单多了。可以先将每个盒子的坐标排成非降序，然后再把整个盒子序列按照如下规则排序
比较第一个坐标，如果想同再比较第二个坐标，如果还相同则比较第三个坐标，依此类推。
这样的依据是把所有可能被第i个盒子包含的盒子都放在第i个盒子的前面，这样才可以进行动态规划。
通过这样的处理以后剩下的就是”最长非降子序列“式的动规了。
时间复杂度O(kn^2)

今天开始准备大学的ACM-ICPC，即使在大学碰不上好的伙伴，也要自己来。
从NOIP2005以后，还没有太多的接触算法方面的东西，今天做了个题，发现手竟然有些生。也快开学了，该好好学，好好努力了。
打算先看几本书，把算法导论再仔细看一遍，还要学好数论，图论，计算几何这几个比较弱的方面。
题目就先做UVA吧，慢慢来，还是先以看书为主。