前言

本身我自己dp学的就不是很好，现在刷几道题有关dp的，每道题总结一下做题的思路。

P2871 USACO07DEC]手链Charm Bracelet

这是一道01背包题，很基础, dp[j]表示的是背包里已经有i的重量，所能拿到的最大价值， 考虑枚举每一个物品， 考虑拿或者不拿，枚举最大重量到本物体的重量， 如果拿的话， 那么当前的重量所能拿到的最大值是dp[ j - w[ i ] + c[ i ], 如果不拿的情况下， 当前的最大重量为dp[ j ], 在这两个之中取最大值就好了， 答案就是dp数组中存的最大的那一个。

为什么第二重循环枚举重量要从后往前枚举：

当j值从 w[j] 枚举到 V 的话， 如果dp[ j - c[ i ] ]被更新掉的话， 那么如果 V 是c[ i ]的倍数或者更大的话， 那么dp[ j - c[ i ] ]将会被转移两次。所以这就成了完全背包了， 但是如果从后往前更新的话就会避免dp[ j ]重复计算的事情发生。

今天按照计划的安排，如期进行了动态规划有关内容的测试。

分数： 80

前言

其实动态规划这天我是挺慌的，因为当初学动归的时候没有任何的基础，其实讲的时候好多基础题都是没思路的，不过还好，有一个系统的学习的机会，把几个基本的动归问题听懂之后，就慢慢的开始有了思路。这算是正式入门了吧。

今天计划讲解的是有关与字符串的有关算法，进行整理一下。

KMP算法

今天首先讲的算法就是KMP算法，这是有关字符串匹配有关问题的一个算法，它可以快速的计算出一个模式串在需要匹配的串中总共出现了几次，并且可以记录每次出现的位置。

其实要达到这个目的有很多办法，但是时间复杂度都比较高，差不多都是高达O(n^3)的级别的算法，而这个KMP算法则可以把时间复杂度降低到O(n+m)左右的范围。

“你上午在机房待了一上午干了些什么？”

“做题。”

“那下午的四个小时呢？”

“当然是做题。”

“晚上呢？”

“做题呀……”

“那你什么时间思考呢？”

以上无聊的老段子你当然可以忽略，但是思考这个问题是绝对不能忽略的。

对拍是什么？简单说就是把两个程序对于同一个输入的输出进行比较，没有问题就再来，有问题就停下来，你就可以找到你程序的问题所在了

很多时候，我们或许有一个标程（或者爆搜程序什么的，反正答案是对的），一个自己的程序，然而一组一组的数据经过我们的手动输入后并没有什么问题，可就是有错……
咋办，一个一个输数据得到什么时候啊，于是，一个很“高端”的东西诞生了——对拍。

关于对拍这个东西，之前的了解并不是很多，因为时间的问题，一场比赛很有可能一份题解都打不出来，更别说要打一份暴力一份正解了。（其实还是因为太弱…）
可是从今以后，需要涉及到的题的算法就更加复杂了，如果费很长时间打了一个不正确的算法，而且也不方便差错，那不就很伤了..于是我觉得要学习一下对拍

以上都是前言

今天按照安排应该是进行一次有关搜索的测试，主要是针对昨天所学的内容

T1

这一道t1其实正解是用二分做的，二分结果即可。
出现的错误：
在比赛时首先没有看清题目，以为每一个瓶盖之间的距离相等，即都是等距的。这直接导致GG，而且在做题的过程中心态并不平和，出现错误查不出来就很烦躁，然后恶性循环下去，这并不是一个好的事情。之后要调整。

今天的主要内容是有关搜索的内容：

但是！

今天其实讲的很水…
有用的东西总结一下：

1. 双向BFS搜索的代码实现

2. 迭代加深搜索的代码实现

3. 可行性剪枝 与 最优化剪枝

4. 爬山算法 与 模拟退火算法(思想)

难点如下：

1. 状态的记录
2. 边界条件的设置

这次分数 50 分

还是贼垃圾。
但是有几点进步的地方。
还是总结一下出现的主要问题：

1. 思考的不够深入，T1很亏.
2. 关于图论的应用，要会建立有关模型.
3. DP 什么的赶紧学，不能再拖了…
4. 端正态度，尽可能拿分，拿分欲望不高

Take my hand now Stay close to me

Be my lover Won’t you let me go

Close you eyes now And you will see

There’s a rainbow For you and me

这是一道图论题：

题面：

H城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴上线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。
　　刘世纪最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路已士
可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士, 这样换乘几次后到达S公园。
　　现在用整数1,2,…N 给H城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为1…S公园巴士站的编号为N。
　　写一个程序，帮助刘世纪寻找一个最优乘车方案,使他在从饭店乘车到S公园的过程
中换车的次数最少。