二楼说一句禁止插楼

B_station这道题，讲了有一个n层的工作站，已知i层有Wi的水，最多可以容纳Li，恐怖分子炸毁i层要用Pi的代价。炸掉i层后。该层的水就会倾泻到i+1层如果某一层的水量，超过了他的容量，则这一层将自动被破坏，所有的水将倾泻到下一层。现在我们的目标是，有个恐怖分子，想用最少的钱毁掉第N层，现在要你知道炸掉哪些层。（1<=n<=15000，0〈=Wi,Li,Pi<=15000）。
假设用Si=W1+W2+...+Wi不妨设恐怖分子炸毁的最高层是第p层，所以第P层的水会不断泻下去，如果存在一个i，满足Wp+Wp+1+....Wi-1+wi<=Li就是说前面几层的水都无法把这一层毁掉，则这一层必须被炸掉。所以我们得到一个需要炸毁的层数的集合，这样就得到了一个O(n平方)的算法。但是一万五的平方肯定是过不了的，但是可得Sp（就是炸完之后往下流的总水量）的值是随着p的增加而递增的，可得Sp-1被包含于Sp-2。所以删除所有的是原先被炸掉层的子集的i（也就是流水量特别大，大于所有的下面层的耐受量的），在这种情况下。我们可以借助大根堆。（是什么玩意明天讲……这算啥……）
基本数据结构希望大家能掌握，这个已经被反映了上去，估计以后会有相关的试题，希望引起注意。

求第一第二第三最短路问题。给了一个无向图，权值是给定的，1~6点的最短路径（图啥的……画不出来，好吧好吧，BS我吧……）第一个路径很简单（dp似乎可以做恩），但是求第二路径，这里我们要用到局部枚举，断掉第一最短路径的某一条边，然后找出来一条最短路，这条路径就肯定大于最小路径。再去恢复，再去断开，然后枚举出来最小值。就是第二最短路径。第三最短路径类似于第二最短路径，在这里再找到一个最小值，这里就是第三最短路径。这就是局部枚举的思想
（接着讲了一道没技术含量的题，结果因为大家想得太复杂，没人想出来，到最后居然是全排列枚举……吐血……）
待续未完，依旧不让插楼的说~~

递推策略：
大家都觉得递推很简单，大家都非常熟悉了，就不拐弯了。一般的形式就是：顺推法，倒推法（我啥都没想到……）。递推的应用有：一般递推问题，组合计数类问题，一类博弈问题，动态规划问题的递推关系。
一般的递推问题比如说很简单的汉诺塔问题。（题目懒得写了）
实数数列，总共是n项，已知a[i]=(a[i-1]-a[i+1])/2+d (1<i<n)(n<60)。这道题我们可以变形得到a[i+1]=a[i-1]-2a[i]+2d（数学变形）然后不断的迭代下去，就能建立a[i]和a[1]和a[2]的关系式，设a[i]-P[i]a[2]+Q[i]d+R[i]a[i]，（经过复杂的我也懒得看太懂的数学变形之后，好吧好吧……我承认我很懒以及上课没好好听什么的，谁叫他写的比数学老师还复杂~哼~）最后能够得到递推关系式，a[n]=p[n]a[2]+q[n]d+r[n]a[1]以及a[2]=(a[n]-q[n]d+r[n]a[1])/P[n]但是按照这个方式去解题的话，会偏离正确值，算法上不会有问题，但是误差很大。因为要用除法。所以以后最好避免开方和除法运算。减少误差。所以最后可以用另外一种数学变形，得到：a[k]=(a[n]-q[n-k+2]d+r[n-k+2]a[k-1])/p[n-k+2]。然后作出来，这个题告诉我们，数学其实在这里也是王道的恩（这句话原话是我说的……）
要了解到的是，在计算机当中，找到一个通项公式，是很难的，只能用递推关系式，否则就是数学题而不是一个程序题目了。

下来讲了一个储油点问题
{原题：
[问题描述]  
一辆重型卡车欲穿过1000公里的沙漠，卡车耗油为1升/公里，卡车总载油能力为500公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立几个贮油点，使卡车能顺利穿越沙漠，试问司机如何建立这些贮油点？每一贮油点应存多少汽油，才能使卡车以消耗最少汽油的代价通过沙漠？  
编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。  
No． distance(k．m．) oil(litre)  
1 ×× ××  
2 ×× ××  
3 ×× ××  
}
这个题顺推是推不出来的，但是倒推是可能的。设way[i]——第i个储油点到终点的（i=0）的距离，oil[i]——第i个储油点的储油量。可得第一个点距离终点就是500KM处，oil[1]=500，为了在i=1储存500公升汽油，至少要开两趟满载的汽油，加上回程这三趟应该刚好耗费了500公升汽油则与第一个点的距离为500/3，再倒推回去，到了i=2，则得到可得至少跑5次，则可得要耗费100公升汽油一趟，则就是路途上耗费的汽油还是500公升，所以可得2到3的距离就是100。推广到一般就可以得到way[k+1]=way[k]+d[k~k+1]=way[k]+500/2k-1。写出递推关系式，进而求解。这就是我们讲的倒推的一个相当典型的例子。


还有一个扫雷的题目，给一列数字，表示附近有多少个雷（就是扫雷的那个数字的意义），然后给了另一列空列。求解第一列雷的摆放方案总数。按照扫雷的经验，可以得知，第二格的状态要用第一格的状态进行推导，所以设a[i]表示序列中的第i个元素，F表示第i格的雷数。就可以递推求解，推算出来递推式之后，可以得知f[1]还是未知的，所以可以得到，设f[1]为0或者1，则总共可能出现的摆法为0,1,2。按照条件的判定进行计算，便可以得到是否有这种情况，总共有几种排法。（看上去的简单题恩，晚上试验一下代码实现，昨天晚上没让人自习，本来就没学好DP，还不让人练，真纠结……）
这就是对于递推的应用，用来解决一般的递推问题


再接着看看博弈问题，走直线棋的问题：现有计算机和人进行人机对弈，有一个1~n的方格，每次可以走k个，谁能最先走到第n格，就算胜利。模拟整个过程设计一个让电脑尽量保持不败的方案。往前倒推，可以得到走到了n-1或者n-2的人必败，则n-3的人必胜。依照此，可得往前倒推，使得每一个取格，都使对方无论怎么走都是输态，如果其中有一步无法达到，则自己呈现必败态。否则，呈现和态。然后确定好每一个取格的状态（必胜，必败，和态）让计算机选择必胜的走格或者和态的走格既可。
这就是在于递推当中的三个应用。

最后看看动态规划中的递推。递推关系其实包含了动态规划，动态规划作为一个特殊的个体，动态规划的动态原因，就是递推。区别在于，一般的递推问题边界条件很明显，动态规划的边界条件比较隐蔽，容易被忽视。其次一般递推数学性较强，动态规划的数学性较弱，最后就是一般的动态规划不划分阶段，动态规划一般有较为明显的阶段。
（DP就这么结束了……好可怜……）
待续未完，依旧不让插楼，恩恩~~

排序问题也是很常见的题目
{原题
排序是计算机科学中一个常见任务。有一种特殊的排序，最多只有3个关键
字。例如，试图对这次竞争的奖牌榜排序时，就只有3个关键字，所有的金牌获得
者在最前面，随后是获银牌者，最后是铜牌获得者。
本题中用1,2,3分别表示3个关键字，需将它们按升序排列。排序是通过一系
列对换操作实现的。一次操作可以交换两个数的位置。
子任务A
请写一个程序，对于一个给定的只含有关键字的序列，计算最少需要几次对换
操作就可以将其按升序排列。
子任务B
输出一种最少次数的对换方案。}
这里有两种情况，一种情况是很直观的，只要交换一次就可以让被交换的两个数字同时归位，还有如果没有这样的数的话，必须多做几次，才能使分别归位。则我们先找到能够进行一次交换就能使两个数字同时归位的数字，然后再进行一个数能够归位的过程，两个过程分别循环。既可求解。


条件变化为如果只能交换相邻的数字的话。则求出来所有数的逆序对就可以了（也是贪心的一种，自行理解……我个人倒是觉得挺微妙的。顺便一提，逆序对即，如果从小到大排序，有10，6，29，则10和6就是逆序对。）
所以我们讲这个题，就是讲到了一个贪心的思想，以及需要注意把条件或者范围更改了之后，就可能不适用了。这就需要我们自己的总结。有些人做的题不多，但是水平很高，就是会总结


贪心标准：（扯了一道条件好长好长，看都看不懂的题，啊啊~~好吧好吧，我承认我懒得看……）很多题目看上去贪心标准是有效的，但是很多情况下，其实是无效的。
现在假设有N匹马，齐王和田忌开始赛马，胜者拿钱，和局无所谓。齐王的马已经安排好了，求田忌该怎么样才能赢得最多的钱。这个题就不讲了，大家自己下去看吧……（这是啥啊……）
恩，未完待续继续不插楼

依旧田忌赛马恩下午继续：现在的情况有三：1.如果田忌剩下的马中，都不能胜过齐王最强的马，那就用最弱的。2.如果最强的马可以赢齐王最强的马，就用最强的赢他最强的。3.如果田忌的最强的马和齐王最强的马可以打平，就用最差的输掉，或者打平（附加：如果田忌最弱的马能够胜过齐王最弱的马，就最强的打平，如果不能，就用最弱的马输掉最强的马，如果最弱的也打平，则就用最弱的对对方最强的马）。但在此刻可以举出反例证明其错误之处（无视括号内，括号内似乎是贪心的正解，姑且按照老师的步调就好……），则就要换方法，换DP。但是DP依旧会超时，所以此题需要先用贪心，然后用DP的时候缩减扫描的范围。从而进行求解，这也是贪心的一种使用的方法。
纯贪心的思路无法达成的时候，要从贪心的思路解放出来，从而达成动态规划。


有一个R*C的矩形网格，每一列恰好有2个白色的方格，和R-2个黑色的小方格。现在要进行一个连续的C次射击，若每一列恰好有一个白色的方格被射中，且不存在无白色方格被射中的行，这样的射击才是正确的。
此题首先用网络流的算法（之后讲解），但时间复杂度和代码的输入太过繁琐。则用第二种方法，贪心：贪心算法不作说明，本题告诉我们生活告诉了我们贪心标准，但是贪心的标准不能想当然的去用。最后就是贪心需要经过严格的证明。在考试中贪心的意义不在于能不能用而在于你敢不敢用……（汗~~！）
贪心由于在大部分时候无法得到最优解，所以贪心的意义精髓在于和其他算法的结合。如：贪心+搜索，贪心+DP。

贪心与动态规划：Peter的快餐店。
原题：
{Peter最近在R市开了一家快餐店，为了招揽顾客，该快餐店准备推出一种套餐，该套餐由A个汉堡，B个薯条和C个饮料组成。价格便宜。为了提高产量，Peter从著名的麦当劳公司引进了N条生产线。所有的生产线都可以生产汉堡，薯条和饮料，由于每条生产线每天所能提供的生产时间是有限的、不同的，而汉堡，薯条和饮料的单位生产时间又不同。这使得Peter很为难，不知道如何安排生产才能使一天中生产的套餐产量最大。请你编一程序，计算一天中套餐的最大生产量。为简单起见，假设汉堡、薯条和饮料的日产量不超过100个。}
假设用P1，P2，P3分别表示汉堡，薯条和饮料的单位生产时间，用t[i]表示每天的生产时间，用P[i,j,k]表示在前i条生产线内，生产j个汉堡,k个薯条的情况下，最多能生产的饮料数。则P[i,j,k]=max{p[i-1,j,k]+r[i,j-j1,k-k1]}，最后求得时间复杂度为十的九次方。所以可得单纯的动态规划是无法完成的。则加入贪心思想，题目当中限定了汉堡饮料等个数不超过一百，则套餐的上限已经限定。在这种情况下，在运行动态规划以前，可以求得最大的套餐数量，限定动态规划的搜索范围。则可以得到更快速的解法。
贪心和搜索：乘车路线
有N个城市用若干的道路相连，每条路上有两个参数，即长度和费用。BOB准备从1到N城市，但是只有W的钱，求在可支付范围下的最短路线。这道题用深搜去搜，在优化的时候，可以预处理一下。算出在I~N不考虑费用的情况下的道最短路径，以及I~N在不考虑路程的情况下的最小费用。设在城市i，已经走过的路程为L，用的费用为W，如果L+minL[i]>=已经找到的最短路径长度，或者W+minw[i]>最大可承受费用，即可进行剪枝，从而进行优化。
NOIP中和图论相关的也就是最小生成树和最短路径的问题。这个例子拿出来的目的是，作为搜索的剪枝的一种手段，也用的是贪心的思想。所以说更多的贪心用在和别的算法进行的结合。贪心的通常用法是给一个界，在这个界里面进行解题。