第一题：给出一串已经拓扑好了的事件，求最短完成时间。

做滥了的题目啊，直接扫一边就出解，O(n)

第二题：给出第二周的歌曲排行榜和每首歌的歌曲排名变化（上升、下降、持平），求前一周的歌曲排行榜的一种可能解。

字符串处理的题目；

首先，我们把上升了的歌看作要把它往下移，而下降了的歌呢就看作要把它往上移，再把所有的持平歌去掉。

那么，现在的排行榜的首位肯定是下，而末位肯定是上了。

现在，找所有下一位是上的下节点。从这个下节点往上延伸到所有连着的下节点，而从这个上节点往下延伸到所有连着的上节点，把这两个模块互换即可。

第三题：你向银行贷款，告诉你你的贷款额、每月还款额和还款月数。求每个月的月利率（每个月银行先算利再让你还钱）

初以为这道题目十分简单，发现不然，这个题目列出来是个高次方程。其实是可以用log函数来解，但是对于有未知数的log函数，Pascal语言显得十分麻烦（几乎不可能实现）。所以，我在考试的时候使用了枚举的方法，得了60%的点。

但是我竟然忘记了世上有二分这样的好方法，其实，以你的总还款额/贷款额的利率（这个是绝对不可能达到的）为上界，下界为0，来二分求解，效果很好。但是虽然二分时间不超，但是发现有一个点竟然超过了int64和extended的届，呵呵。

第四题：走迷宫变形，有起始朝向，就是一秒钟内可以走1格、2格、3格，而且向左向右转也要耗费一秒。

爆容易的题目，难得写了。只有50×50的大小，不说广搜，深搜都能过啊。

课后孟LJ简单阐述了下搜索的优化，无非以下三种：

1、双向广搜（省时一半，较容易实现）；

2、普通判断剪枝（子树）；

3、估价函数剪枝（A*）。这种做法需要良好的估价能力，适合要打路径的题目。估价函数是一个可以求出从当前状态到目标状态的大概花费的函数，其值必须小于等于真实花费。所以，当走到一个（当前花费+估价花费>已知最小花费）的点时，完全可以把他的子树剪掉。这就是一种动态剪枝方法。效果甚佳，但本人未实现。

题一   进制转换：

负进制，短除法，但是余数小于0时要从上一位借位（商+1，余数-进制数）（LRJ大牛提出）

题二   乘积最大：

动规+递归

设d(i,j,k)为第i-j个数字中用k个乘号所取得的最大乘积。

转移方程（我直接用递归调用 ^_^）：

d(i,j,k)=max{数(第i到第t个字)*d(t,j,k-1)}   (i<=t<=j-1)

临界：所有k=0的值就为原来的值。

题三   单词接龙：

求出一张表示每两个单词（有序）之间的增长字母数的表，根据这张表枚举第一个单词来搜。居然全不超时。但是发现有的单词可以用两遍，囧。

题四   方格取数：

一直没想通。LRJ的报告太草了。飞机的报告里面是“广搜式Dp，效率还不错。可能数据比较弱。”，囧；

Google了一下，发现“上帝的右手”大牛的报告不错：

两条路线同时进行的动态规划

阶段：按所走的步数来分阶段，从左上角走到右下角，共2n-1个步骤，故共2n-1个阶段。但，有两条线路，故每一阶段的状态都会复杂一些。

状态：有两线路同时走，在某阶段的某状态，要用两个坐标来分别表示两线路的两个点。如：第一阶段，共一个状态：(1,1),(1,1)；第二阶段，(1,2),(1,2);(1,2),(2,1);(2,1),(1,2);(2,1),(2,1)共四个状态。

　　由于在第k阶段的任何两个点的x,y坐标是有关系的：k+1=x+y。故可只用ｘ坐标来表示一点的坐标，故状态可表示为(x1,x2)，对应的y坐标为：y1=k+1-x1,y2=k+1-x2。

决策：若用0,1分别表示向下或向右走，则每个状态的可能决策有四种：(1,1),(0,0),(1,0),(0,1)。两个数值分别表示两个点的下一步走向。

状态转移方程：

　　设map(x,y)为方格图，f(k,x1,x2)表示第k个阶段走到(x1,x2)状态的最大和

　　f(0,1,1)＝map(x1,1+1-x1)　即map(1,1)

　　f(k,x1,x2)=max{f(k-1,x1′,x2′)+map(x1,y1)｜x1=x2，f(k-1,x1′,x2′)+map(x1,y1)＋map(x2,y2)｜x1<>x2}　(x1′,x2′)表示可通过某决策到达(x1,x2)的所有点

明天再把第四题实现一下，就要进入恐怖的2001后了。。。

Welcome to WordPress. This is your first post. Edit or delete it, then start blogging!

Bottom post for my other posts in other website and BSPs.