poj3373 Changing Digits
经过几天不屈不挠地思考这一题，最后还是不会，主要是想不到判重的方法。看了解题报告，正确来说，是代码。然后发现一直想不通的问题竟然是那么简单地被解决（用余数判重）。这个涉及到模n同余的特性。另外的两点就是搜索的顺序和高精度。搜索的话要按照以下规则：
1.从最高位开始，逐渐往低位搜；
2.先搜小于原来的数的，然后搜大于原来的数的；
3.先搜一位，然后两位，如此类推。
这样一来就可以保证第一个搜到的答案就是要求的答案。但是就这样直接算的话，还是会超时。所以需要优化一下。主要优化的地方就是求大数的余数的方法。
poj3411 Paid Roads
最近rp真是出了点问题。身边发生了许多不顺心的事情。现在连做一道题都用了那么久时间。
首先说说题目大意：有一些点，然后有些点有边，每条边有两个权值，一个是普通的权值，一个是必须经过某些点后才能用的权值。
然后思路：其实这题就是搜索题。关键是状态的定义：f[i][j]表示从1到 j状态为i的最少费用。其实已经做过几题类型的，但是想状态的时候还是用了不少时间。看来对于知识的迁移还是不够，对增加维度来减少问题复杂度这个思想还是不是很熟悉。
poj1724 Roads
经过无数TLE，终于让我用超级广搜过了这一题
（这题其实和sicily的1702差不多思路）。这题的主要难点有两个，1.存放图，2.剪枝。由于同一对点有可能有多条边，所以直接用二维数组是不可行的。然后最容易想到的是用邻接表。然后就是搜索了。搜索的话，我是用一个二维数组dist[i][cost]来记录从原点到i这一点耗费为cost时的最短路径。这样一来，最终的结果就是dist[n][]中的最小值。剪枝方法就是：当当前结点的的距离小于dist[][]相应值时，才把结点放入队列里面，当然不能忘记的是当前的金钱耗费不能大于k。但是仅仅这样是不够了。这样只会TLE。整个上午就纠结在如何剪枝上，结果还是没什么收获，就去吃饭&看动漫，看完之后突然灵机一闪，发现可以用一个变量minimum记录d[n][]中的最小值，然后如果当前的距离如果不小于minimum的话，就不能加入扩展队列。加上这个剪枝后，终于AC了～哈哈
poj1836 Alignment
这题对题意的理解是一个关键。一开始以为是求最大递增序列或最大递减序列，然后看discuss，发现是求一个序列，该序列中有一个最大值max，然后从0到max是递增的，然后max+1到n-1是递减的。一开始的时候，用了超级暴力的dp，然后tle了，之后发现可以通过预处理来减少时间耗费。先分别从0到n-1和n-1到0求出LIS。之后枚举中间最大值，求出相应的那个序列的长度，再从所有长度中求出最大值，这个值就是最长的符合要求的序列。最后就只要用n减去那个数，就是要出列的人数了。
poj3267 The Cow Lexicon
最近把黑书中关于dp的部分粗略地看了一下，还是不会做dp的题目，泪奔～～～～～～～不过感觉就或多或少还是有的……
这题我一开始想到的状态表示方法是：d[i]表示0～i的字符串里面最少要删除的字符数。然后写了很久，debug了很久，还是WA。之后上discuss看了一下，发现其实只要逆着看状态，就好写很多。把d[i]表示从i到l-1的字符串里面最少要删除的字符数。
然后状态转移方程是：
f(i) = min{ d+f(k), f(i+1)+1 }。
d:表为匹配单词而删的字符数(如果可以匹配)；
k:表匹配后单词的下一个位置；
d+f(k):表保留第i个位置字符的情况；
f(i+1)+1:表不保留第i个位置字符的情况。