Neverland

受Livia影响，最近迷上了Lube这个俄罗斯民谣摇滚乐队。

摇滚乐队也不一定要搞得像反政府武装，就像Lube，是一个完完全全的主旋律乐队，歌颂的都是我们劳动人民，光荣的劳动人民！

这个乐队能让那些曾经生活在东北的人们，或者说生活在受俄罗斯文化影响的地区的人们，一瞬间记起红汤和大列吧的味道。力荐！

我想念哈尔滨了，我也想念你们，哈尔滨的牛鬼蛇神们。

你知道《Davai Za》中第5首歌Бабушка里最后的“亚留不留节别呀”是什么意思吗？

Once it has began, won’t stop until it’s done.

                                                 ------Norah Jones

做人其实很无奈，在国内很无奈，在国外也一样，不要想就好。

                                                 ------偷渡客

有时候，大道理就是这么简单，这么俗。

在这个不是假期的假期，我每天都起得出奇的早，当然，是相对于以前的我。个中原因，我想，她是知道的。

昨晚躺在床上浏览着PSP中她的照片，纠结着照片的清晰度，睡着的时候可能已经3点了。

所以，今天的晚起是个例外。

平静湖面上的两粒花粉，它们碰在一起的概率可想而知，或许是可想，而不可知。

我和她，如果单靠自己无趋向性的布朗运动，情况可能还不如那两粒花粉。

还好，有那次北京之行，还好，我们都花了那笔“冤枉钱”。

于是，有了每天一起或食堂或面馆的午餐，一起四惠-阜成门的地铁，一起的西单书店，一起的天文馆……

也有些许遗憾，我错过了本该一起的晚餐，并留下了没有回赠礼物的窘态。

不过，这些在后来多多少少得到了补偿。

之后，又有了那些电话和信息，和拖欠了很久的上海之行。

当然，也包括那些难以总结，却最为珍贵的点滴们。

过去的一年多里，我总是咬牙切齿的抱怨运气不太好。

还好有她，让我又觉得运气好像也没那么差，连花去的那笔对GRE成绩没起多大作用的学费，也变得不冤枉了。

现在，我总感觉庆幸，自己那原本混乱的美国梦，逐渐变得清晰，更重要的是，我又有了一个新的实现它的理由：

See Dirac Sea directly.

下午在公交车上，耳机里响着Amorphis主唱低沉的深喉嘶吼，脑子里又开始放那些她主演的剧了。

那些剧其实没停播过，插播广告也不多。

Lust

Gluttony

Greed

Sloth

Wrath

Envy

Pride

下载Amorphis专辑的时候，得到了意外收获，好心人的种子里包含了Amorphis现场的照片。如下所示。        

最好的朋友今天滚了。

早上迷迷糊糊的听见短信，“别了，哈尔滨。别了，好哥们……”

他那时候刚上车。我没去送他，心里的滋味有点儿奇怪。

这些天，同学们陆陆续续的离开哈尔滨，直到今天，他走，我才稍微有了点儿离别的感觉。

想起和他一次次半夜吃饭喝酒，一起被人打，聊电影聊音乐，听他侃哲学侃历史……

一晃3、4年就这么过去了，真他娘的快。

下次见面，或者在哈尔滨见面，不知道要等多久了。

愿他能滚向吃饱喝足、吃香喝辣，并能够相对正确的浪费生命！

朋友间流行起了QQ签名档大比拼，在最近几场的“签名档战役”中，石头同学取得了全面胜利。

1、蓝白战役

天哥：“又想驴跑，又要小驴不吃草。”

石头：“天哥，你out啦！新时代的‘又想驴跑，又要小驴不吃草。’应该说成‘又想把石头喝倒，又不请石头吃烧烤。’”

天哥：“……”

蓝白战役中，石头同学仅一招就将蓝天同学击败。

2、白杨战役

石头：“白先生喜欢吃李先生。”

杨同学：“杨先生喜欢和白先生吃李先生。”

杨同学：“李先生开始吃白先生和杨先生。”

杨同学：“杨先生先生，白先生后生。”

一直被杨同学压制，石头同学实在忍无可忍了……

石头：“虽然杨先生比白先生先生，但是白先生称呼杨先生为后生。”

白杨战役是防守反击的典范。

整理资料时，发现一两年前写的一份作业，其实就是后来流产了的技术交流报告。现在看来，那时候是真够幼稚的，居然幻想着实验室的老师和同学们会花时间看，真是可笑。贴出来，博看官一笑。

----------------------------幼稚的分割线---------------------------------

算法优化对于程序的作用分析

在我们学习的过程中，要面对各种类型的实际问题。而在处理这些问题时，首先，也是最重要的就是要将它抽象为数学模型，这样才能让我们所学习的理论知识有的放矢。然后就是要设计解决问题的策略，也就是我们常说的算法。最后，要对解决问题的算法进行优化。

建模和算法设计的作用显而易见，他们是程序设计的灵魂。在建模失败的前提下，其它后续工作都是徒劳。算法设计可以使我们的程序在占用尽量小空间和花费尽量少时间的情况下解决问题。而算法优化的作用就比较模糊，有时甚至显得微不足道。

然后，实际情况并非如此。在本文中，将结合曾经做过的一个编程题目对算法优化的作用进行分析。

1 题目介绍

为了说明算法设计的思路，首先将对题目内容进行介绍。

在芯片设计过程中，每个芯片中包含多个功能模块，而各个功能模块之间有输入和输出引脚。为了实现所要设计的芯片的功能，我们要将各功能模块之间所对应的引脚连接起来。如图1所示。

图1左图表示出了两功能模块间引脚的对应关系。为了实现芯片中各功能模块的最佳布局，两功能模块引脚间连线中，最大不相交连线数目对芯片设计工程师是极为重要的。如图1右图所示，图中最大不相交连线数目为3。

本题目要完成在给出任意两模块间引脚对应关系的情况下，计算出最大不相交连线数。

2 题目分析

本题目是一个典型的DP(Dynamic Programming)问题。整个问题的解决定于其子问题的解。

首先，要将问题抽象为数学模型。在两模块间连线中，我们设左侧第1个到第i个引脚的集合与右侧第1个到第j个引脚集合间连线的最大不相交连线数为Area[i, j]。设左侧第i个引脚与右侧第j个引脚的连线数为Edge[i, j]，当两引脚中有连线时，Edge[i, j]值为1，否则为0。

通过以上分析，很容易得到该DP问题的状态转移方程：

Area[i+1, j+1]=max{Area[i, j+1], Area[i+1, j]}+Edge[i+1, j+1]

通过该状态转移方程，我们可以递归的计算出整个问题的解。

2.1 基本程序设计过程

在程序编写过程中，我们可以用循环来遍历左右引脚集合，如下式所示。将每次循环所得的结果保存在一个表中，循环结束时即可得到问题的解。

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{ …… }//n为引脚数目

对于图1中所示的情况，遍历过程及每次循环的结果如表1所示。

                                                                                                                 表1  示例

由表1所示，图1所示的情况，最大不相交连线数目为3。由于程序对于i和j进行了遍历，所以此算法为O(N²)。确立此算法后，在时间要求不是很严格的情况下，就可以得到问题的解。

2.2 算法优化

此前提到，求解该问题的基本算法为O(N²)，所以当数据量很大时，计算量和运行时间也是相当惊人的。如果仔细分析题目特征，会发现可以对其进行优化。

观察表1中所示的数据，可以发现：只有当Edge[i, j]值为1时，才能对整个表格中的数据造成影响。这一点也可以通过证明来得到。了解了这个特征，就可以对基本的算法进行优化。

每个最大不相交连线数的值在表中都对应了一个开始的位置，如在表1第4行中，值为1的最大不相交连线数开始于j为2的位置，而值为3的最大不相交连线数开始于j为3的位置。而这些值的开始位置，都是由Edge[i, j]为1的位置决定的。

根据以上分析，我们就可以设置一个表Position[t]用来保存值为t的最大不相交连线数所对应的开始位置。如在表1第1行中，Position[1]=4。在第i行中，只有一个j_i值使得Edge[i, j]为1，我们可以在1~t_max（t_max值为此刻的最大不相交连线数目）范围内将j_i与Position[t]的值进行比较，当Position[t]<j_i<Position[t+1]时，将Position[t+1]值改为j_i，并不断更新t_max的值。当遍历完每一个i值后，最后所得到的t_max即为问题的解。

对于每个i，将j_i与Position[t]的值进行比较的过程可以通过二分法查找，二分查找算法为O(logN)。所以遍历所有i的算法为O(N*logN)。与基本算法的O(N²)比较，优化后的算法有了很大的改进。用基本算法需要超过1秒的时间所解决的问题，优化后的算法只需要0.1秒就能够完成。

3 小结

在上述的例子中，我们所设计的优化方法将算法相对复杂度从O(N²)降低到O(N*logN)。这说明了在建立数学模型和基本算法设计正确的前提下，算法优化有时会对程序起至关重要的作用，尤其是在那些对算法速度、计算准确度和占用空间要求高的情况下。

文中所提到的题目请详见acm.hit.edu.cn网站上Problemset中的1288题。

附录

#include<stdio.h>

int main()

{

     int n, p, Pin[40001], Left[40001], Area[40001], i, j, left, right, middle, solution;

     scanf("%d",&n);//n为问题数量

     for(i=0;i<n;i++)

     {

          scanf("%d",&p);//p为引脚数量

          for(j=1;j<=p;j++)

          {

               scanf("%d",&Pin[j]);

               Left[Pin[j]]=j;

               Area[j]=-1;

          }

          Area[1]=Left[1];

          left=1;

          right=1;

          middle=1;

          for(j=2;j<=p;j++)

          {

               if(Left[j]<Area[left])

               {

                   Area[left]=Left[j];

                   solution=right;

               }

               else if(Left[j]>Area[right])

               {

                   right++;

                   solution=right;

                   Area[right]=Left[j];

               }

               else

               {

                    while(1)

                    {

                         middle=(left+right)/2;

                         if(Left[j]>Area[middle])

                         {

                              if(right-middle<=1)

                              {

                                   Area[right]=Left[j];

                                   break;

                              }

                              left=middle;

                         }
 
                         else if(Left[j]<Area[middle])
 
                         {

                              if(middle-left<=1)

                              {

                                   Area[middle]=Left[j];

                                   break;

                              }

                              right=middle;

                         }

                    }

               }

               left=1;

               right=solution;

          }

          printf("%d\n",solution);//solution为问题的解

      }

      return 0;

}

为space背景《少年》音乐填词如下：

你在干啥？

我在看花。

看花干啥呀？

没啥。

为了方便五音不全者演唱，现将音调加入歌词，创作出“所见即所得”的歌词如下：

捏栽甘傻？

喔栽堪花。

堪花甘撒呀？

抹撒。