资源描述
搜索与动态规划搜索与动态规划基础基础搜索与动态规划基础1我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 深度优先搜索深度优先搜索深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.l递归，回溯，暴力。l就像走迷宫，走遍任何一条路径，碰到死路。l走不了了，就回头找到最近的分叉路，走另一条。以此类推，直到找到出口。所以相当暴力，基本上比赛不会出太赤裸裸的暴力搜索。l用暴力搜索的要小心的估算复杂度，不轻易写。深度优先搜索深度优先搜索属于2我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物递归递归l#includelusing namespace std;lint f(int x)llif(xx)lcoutf(x)endl;lreturn 0;l递归#include3我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 树树l搜索到有的点，当树层数稍微多时，指数级增长复杂度.#!(#)*$)!(*#(条件剪枝！树搜索到有的点，当树层数稍微多时，指数级增长复杂度4我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物递归递归:回溯方法回溯方法l例：皇后问题QQQQ递归:回溯方法例：皇后问题QQQQ5我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3.回溯方法回溯方法()()3.回溯方法()()6我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3.回溯方法回溯方法()()(1,1)Q3.回溯方法()()(1,1)Q7我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3.回溯方法回溯方法()()(1,1)(1,1)(2,3)QQ3.回溯方法()()(1,1)(1,1)(2,8我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3.回溯方法回溯方法()()(1,1)(1,1)(2,3)Q3.回溯方法()()(1,1)(1,1)(2,9我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3.回溯方法回溯方法()()(1,1)(1,1)(2,3)(1,1)(2,4)QQ3.回溯方法()()(1,1)(1,1)(2,10我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3.回溯方法回溯方法()()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)QQQ3.回溯方法()()(1,1)(1,1)(2,11我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3.回溯方法回溯方法()()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)QQ3.回溯方法()()(1,1)(1,1)(2,12我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3.回溯方法回溯方法()()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q3.回溯方法()()(1,1)(1,1)(2,13我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3.回溯方法回溯方法()()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)3.回溯方法()()(1,1)(1,1)(2,14我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3.回溯方法回溯方法()()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)(1,2)Q3.回溯方法()()(1,1)(1,1)(2,15我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3.回溯方法回溯方法()()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)(1,2)(1,2)(2,4)QQ3.回溯方法()()(1,1)(1,1)(2,16我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3.回溯方法回溯方法()()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)(1,2)(1,2)(2,4)(1,2)(2,4)(3,1)QQQ3.回溯方法()()(1,1)(1,1)(2,17我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3.回溯方法回溯方法()()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)(1,2)(1,2)(2,4)(1,2)(2,4)(3,1)(1,2)(2,4)(3,1)(4,3)QQQQ3.回溯方法()()(1,1)(1,1)(2,18我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3.回溯方法回溯方法l递归的思想：当前状态目标状态g3.回溯方法递归的思想：当前状态目标状态g19我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物Hdu 2510 符号三角形符号三角形http:/ 第1行有n个由“+”和”-“组成的符号，以后每行符号比上行少1个，2个同号下面是”+“，2个异 号下面是”-“。计算有多少个不同的符号三角形，使其所含”+“和”-“的个数相同。n=7时的1个符号三角形如下:+-+-+-+-+-+-+-+Hdu 2510 符号三角形http:/acm.hdu.20我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 怎么做怎么做l递归：dfs(int row,int val,int plus,int min);l建立一个数组，暴力填写+和-，最后判断是否合法。合法就num+。l这个思路很容易想到，想到后马上看数据范围，n=24，貌似不大。暴力写写，挂了。l打表吧。还是不行，跑不出结果怎么打表，囧l剪枝！计算出一共会有多少个+，这样一旦+或者-的数量超过这个数，就可以回溯了。怎么做递归：dfs(int row,int val,in21我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 n=24l#include using namespace std;int a=0,0,0,4,6,0,0,12,40,0,0,171,410,0,0,1896,5160,0,0,32757,59984,0,0,431095,822229;lint main()l int n;while(cinn,n)coutnanendl;return 0;n=24#include usin22我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物Pku 1088 滑雪滑雪 lhttp:/ x,int y)l如果dpxy=-1 进行计算，不然返回dpxyl计算时,dpxy=max(ldfs(x-1,y),dfs(x+1,y),dfs(x,y-1),dfs(x,y+1)l)+1;l(如果周围比它小的话)Pku 1088 滑雪 http:/acm.pku.e23我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物推荐题目：推荐题目：lFoj：l1408l1734l1543推荐题目：Foj：24我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 广度优先搜索广度优先搜索bfsbreadth-first search 14513211671615124*2820113917191018如果*想碰到，需要多少步。DFS写写看吧。Bfs用队列。Struct nodeInt x;Int y;Int num;Bool flag100100;广度优先搜索bfsbreadth-first searc25我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物Hdu 3220 Alices Cube l上海赛区的题目，清华10+分钟过的题目，全场100+多队，几乎所有的队伍都过的题目，但是做出来的速度却相差很多。40分钟内写出来，并一次ac的。lHdu 3220，会的可以去写写。lBfs+位压缩。http:/ 3220 Alices Cube 上海赛区的题目，26我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物题目大意：题目大意：给定一个几何体，每个点都有一个值，0或者1，每次可以把线段相邻的两个点的值互换，问需要几步，可以让1-8号节点是0，而9到16号为1题目大意：给定一个几何体，每个点都有一个值，27我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物做法做法l首先，肯定要很认真的看清哪些点是相邻的，为了提高ac率，要检查两三遍。l比赛场上有人没用位压缩的，肯定超时了，后来跑了很久后，终于打表过。浪费很多时间。l对于16个点，int 有32位，我们可以令每一位对应好节点号，比如3 就是0.011这样每次送入队列的只是一个数字，这个数字就能用16个点的信息，如果用结构体，里面再定义bool flag【16】，就会超时。做法首先，肯定要很认真的看清哪些点是相邻的，为了提高ac率，28我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物做法做法l未压缩的目标状态：256-1=255l初始态：自己用二进制转十进制法转得到x；struct node int num;int zt;用到stl 开始时s.num=0;s.zt=x;做法未压缩的目标状态：256-1=25529我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 做法做法(伪代码伪代码)lQ.push(s);lWhile(!q.empty()llTmp=q.front();lQ.pop();l该变一步，得到tmp2 tmp2.num=tmp1.num+1,q.push(tmp2)；lIf(tmp2.zt=目标状态)打印num；break;l 做法(伪代码)Q.push(s);30我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 广度优先搜索广度优先搜索lBfs 用在地图搜索的非常多。l如何提高效率。以题目而定。l常用：优先队列优化。就是（堆）l例子：草地-2平地-1草地-2草地-2雪地-3平地-1平地-1雪地-3雪地-3雪地-3草地-2平地-1 广度优先搜索Bfs 用在地图搜索的非常多。草地平31我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物Bfs 简介简介lBfs 用队列的思想，先进先出。lHdu 1242 Rescuelhttp:/ 简介Bfs 用队列的思想，先进先出。32我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物做法两种做法两种l1：记忆化bfs，用一张二维表，存到达每个点所要的最短步数，初始化为inf(无穷大);每次用bfs到达的步数如果小于该点的原值，更新，并入队。直到队列为空；l2：优先队列，每次选取步数最少的点出来，第一次到达目标点的步数就是最小步数。做法两种1：记忆化bfs，用一张二维表，存到达每个点所要的最33我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物Bfs 用到的用到的stl。l#includelStruct nodelint x,int y,int num;lqueueq2;lpriority_queueq1;l可以自动选取优先级最高的点出来扩展。比如上题中的消耗体力最少的点出来扩展。提高效率。Bfs 用到的stl。#include34我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物Priority_queuel其实就是数据结构将会学到的“堆”，能在log级的复杂度内找到最小的值，并调整堆。l自己写堆效率较高，代码量大。且复杂容易出错。一般情况下stl的这个函数效率也足够高了。很方便。l结构体小于号重载后，每次选取步数最小的点出来。Priority_queue其实就是数据结构将会学到的“35我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物Bfs题目：题目：lFzu 1205lPoj 1724lHdu 2267Bfs题目：Fzu 120536我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 A*算法算法 A*算法37我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 动态规划动态规划 不得不说的例子：数字三角形 动态规划 38我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物动态规划与递归动态规划与递归l动态规划思想：l求c(n,m);l递归写法：lint c(int n,int m)llif(m=0)return 1;lif(m=1)return n;lif(n=m)return 1;lreturn c(n-1,m-1)+c(n-1,m);l动态规划与递归动态规划思想：39我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物动态规划写法动态规划写法lfor(i=0;in;i+)llfor(j=0;j=i;j+)llif(j=0|i=j)lCij=1;lelselCij=Ci-1j+Ci-1j-1;ll动态规划写法for(i=0;i=1;i-)lFor(j=1;j=1;i-)43我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物不得不说的另一个例子：背包问题不得不说的另一个例子：背包问题lHdu 2602 Bone Collector lhttp:/ 2602 Bone C44我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物0-1 背包背包l题目模型：lN个物体：两个属性：重量和价值l如上：5个物体，背包容量10个重量l5个物体的价值：1 2 3 4 5l重量 5 4 3 2 1l如何选取其中的物体，使价值和最大，当然重量又不能超过背包的最大允许量。0-1 背包题目模型：45我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物动态规划动态规划每次加入一个物体的考虑，只有取与不取的情况，保留最大值。弄懂思想代码很短。初次接触则不好懂n个物体，m的背包容量lfor(i=0;i=wi;j-)ldpj=max(dpj,dpj-wi+vi);动态规划每次加入一个物体的考虑，只有取与不取的情况，保留最大46我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物无穷背包无穷背包l只要从小往大dp就行了lfor(i=0;in;i+)lfor(j=0；j=m;j+)ldpj=max(dpj,dpj-wi+vi);无穷背包只要从小往大dp就行了47我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 USACO2.2 Subset Sumsl题目如下：l对于从1到N的连续整集合合，能划分成两个子集合，且保证每个集合的数字和是相等的。l举个例子，如果N=3，对于1，2，3能划分成两个子集合，他们每个的所有数字和是相等的：l3and 1,2 l这是唯一一种分发（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）l如果N=7，有四种方法能划分集合1，2，3，4，5，6，7，每一种分发的子集合各数字和是相等的:l1,6,7 and 2,3,4,5 注 1+6+7=2+3+4+5 l2,5,7 and 1,3,4,6 l3,4,7 and 1,2,5,6 l1,2,4,7 and 3,5,6 l给出N，你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出0。程序不能预存结果直接输出。USACO2.2 Subset Sums题目如下：48我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物解法：解法：lint s=n*(n+1)/2;if(s%2)cout 0 endl;lfor(i=1;i=i;j-)ldpj+=dpj-i;lcout (dyns/2)endl;解法：int s=n*(n+1)/2;if(s%249我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物图论和动态规划图论和动态规划lFzu 1747 Impossible Mission lhttp:/ 1747 Impossible Mis50我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物求哈密顿通路求哈密顿通路1234 4 1 4 1 2 1 3 2 3 4求哈密顿通路1234 4 1 4 451我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物l位运算，比如3，位表示0011，为已经走过1号点和2号点的情况。l定义二维数组dpab,表示到a点，此时共走过b的状态的走的种数。l假设已知dp300101,lDp200111,dp401101,dp510101l都要加上dp300101;位运算，比如3，位表示0011，为已经走过1号点和2号点的情52我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物fzu动态规划动态规划lFoj 1342lFoj 1667lFoj 1416fzu动态规划Foj 134253我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 结束结束l谢谢 结束谢谢54
展开阅读全文