经典算法（15） “一步千里”之数组找数

2016年07月27日 39 阅读

经典算法（15） “一步千里”之数组找数2014-01-03 csdn MoreWindows首先看看题目要求（题目来源：http://weibo.com/lirenchen，特此鸣谢）：有这样一个数组A， 大小为n，相邻元素差的绝对值都是1。如：A={4,5,6,5,6,7,8,9,10,9}。现在，给定A和目标整数t，请找到t 在A中的位置。除了依次遍历，还有更好的方法么？这道题目的解法非常有趣。数组第一个数 为array[0], 要找的数为y，设t ...

算法：uva-1427 Parade （单调队列优化dp）

2016年07月27日 38 阅读

算法：uva-1427 Parade （单调队列优化dp）2014-01-03 csdn shuangde800题意F城由n+1个横向路和m+1个竖向路组成。你的任务是从最南边的路走到最北边的路，使得走过 的路上的高兴值和最大（注意，一段路上的高兴值可以是负数）。同一段路不能经过两次，且不能从北往南 走。另外，在每条横向路上所花的时间不能超过k。思路这题在uva和LA上又是不能评测， 于 是在hdu和poj上评测了这题这题状态比较容易想到, f（i, j）...

算法：uva-10304 Optimal Binary Search Tree（区间dp）

2016年07月27日 38 阅读

算法：uva-10304 Optimal Binary Search Tree（区间dp）2014-01-03 csdn shuangde800题意给一个序列即可 S = （e1,e2,...,en）,且e1<e2<..<en.要把这些序列构成一个二叉搜索 树。二叉搜索树是具有递归性质的，且若它的左子树不空，则左子树上所有结点的值均小于它的根结点的 值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。因为在实际应用中，被访...

算法：uva 437 - The Tower of Babylon（DAG最长路）

2016年07月27日 33 阅读

算法：uva 437 - The Tower of Babylon（DAG最长路）2014-01-03 csdn shuangde800题目大意有n种长宽高为x,y,z的砖头，每种都有无数个。砖头可以用不同姿势的方向来盖 。砖头a以某种姿势可以盖在砖头b上，当且仅当a的底部的长宽都要比b的底部长宽要小。问 最高可以建多高？思路对于一个x,y,z砖头，它可以有3中姿势放置。（前两个为地面 ，后一个为高）x, y, zx, z, yy, z, x把每种姿势都记...

算法：UVA 473 - Raucous Rockers （dp）

2016年07月27日 33 阅读

算法：UVA 473 - Raucous Rockers （dp）2014-01-03 csdn shuangde800题意有n首歌，每首时长Ti，要把这n首歌装进m个光盘里面，每个光盘最多能存的时长为t要求这些歌在光盘里面要按照所给歌的先后顺序存入，不能改变前后顺序。例如有4首歌，按顺序给出他们的时长：1，2，3，4.装入一个容量时长为10的光盘里， 可以是1，2，3或者1，3，4等，但是不能2，1，3问最多能存几首歌？思路：用f[i][j][k]表示前...

算法：uva 662 Fast Food （dp）

2016年07月27日 37 阅读

算法：uva 662 Fast Food （dp）2014-01-03 csdn shuangde800题意一条直线马路上有n个饭店，各个坐标为di.要在n个饭店中选择k个饭店用来建造停车 场。没有建停车场的饭店，只能使用附近最近的一个停车场。问总距离最少的建造方案，并输出。思路先进行预处理，sum[i][j]表示在饭店i～j之间建一个停车场，i～j的所有饭店到停车场 的距离之和最小。在饭店i～j之间，选择在（i+j）/2点建造是总距离最小的方案f[i][...

算法：uva 672 Gangsters（ dp ）

2016年07月27日 35 阅读

算法：uva 672 Gangsters（ dp ）2014-01-03 csdn shuangde800题目大意：有个酒店的门会改变尺寸，变化范围是【0，k】，这个门每秒钟尺寸可以变大1，可以 减小1，也可以不变。现在有n个人，他们的尺寸为si，每个人在ti时刻想要进入酒店，只有在ti时刻 酒店门的尺寸恰好和这个人的尺寸大小相等，这个人才可以进入。每个人有一个值Pi，当某人进入酒 店，酒店就会增加Pi值。在[0,T]这段时间内（0秒时酒店的门尺寸状态是0...

算法：uva 1169 - Robotruck （单调队列优化dp）

2016年07月27日 36 阅读

算法：uva 1169 - Robotruck （单调队列优化dp）2014-01-03 csdn shuangde800题目大意（LRJ《训练指南》）有n个垃圾，第i个垃圾的坐标为（xi,yi），重量为wi。有一个 机器人，要按照编号从小到大的顺序捡起所有垃圾并扔进垃圾桶（垃圾桶在原点（0,0））。机器人可以捡起几 个垃圾以后一起扔掉，但任何时候其手中的垃圾总重量不能超过最大载重C。两点间的行走距离为曼哈顿距离 （即横坐标之差的绝对值加上纵坐标之差的绝对...

算法：UVa 1252 - Twenty Questions（记忆化搜索，状态压缩dp）

2016年07月27日 33 阅读

算法：UVa 1252 - Twenty Questions（记忆化搜索，状态压缩dp）2014-01-03 csdn shuangde800题目大意有n个长度为m的二进制串，每个都是不同的。为了把所有字符串区分开，你可以询问，每次可以问某位上是0还是1。问最少提问次数，可以把所有字符串区分开来。思路f[s1][s2]: 表示提问的问题是{s1}集合，答案是{s2}时，还需要问几次才可以全部区分开当问题集合为{s1}时， 如果还不能区分所有答案，那么就需要...

算法：uva 1291 - Dance Dance Revolution （ dp ）

2016年07月27日 36 阅读

算法：uva 1291 - Dance Dance Revolution （ dp ）2014-01-03 csdn shuangde800题目大意如上图，这是一个跳舞机，初 始状态两个脚都在0, 状态表示为（0, 0）, 然后跳舞机会给你一系列舞步方向，例如 2,3,4,2,3.......每次你必须选择一只脚移动到对应数字方向的各格子上。例如从初始状态 （0,0）,要移到1, 可以选择左脚或者右脚移上去，对应的状态为（1, 0）, （0,1）有一个限制...

算法：UVa 1292 - Strategic game （树形dp）

2016年07月27日 38 阅读

算法：UVa 1292 - Strategic game （树形dp）2014-01-03 csdn shuangde800题目大意给定一棵树，选择尽量少的节点，使得每个没有选中的结点至少和一个已选结点相邻。思路经典的树形dp题，据说是最小顶点覆盖。f[u][0]: 表示不选i点，覆盖这个子树 的最少点f[u][1]：选i点，覆盖这个子树的最少点对于u点，如果选择这个点，那么他的 字节点可选也可不选如果不选u点的话，那么它的子结点就必须要选！开始时我以为字...

算法：uva 1351 String Compression（字符串区间dp）

2016年07月27日 34 阅读

算法：uva 1351 String Compression（字符串区间dp）2014-01-03 csdn shuangde800题目大意给一个字符串，可以把连续相同的部分进行缩写成k（S）的形式，S是一个字符串，k表示 有连续相同的S例如，abgogogogo，可以缩写成ab4（go）. 还可以嵌套缩写，比如“nowletsgogogoletsgogogo”， 缩写成“now2（lets3（go））”思路...

算法：UVa 1366 - Martian Mining （dp）

2016年07月27日 35 阅读

算法：UVa 1366 - Martian Mining （dp）2014-01-03 csdn shuangde800题目大意给出n*m网格中每个格子的A矿和B矿数量，A矿必须由右向左运输，B矿必须由下向上运输 ，管子不能拐弯或者间断。要求收集到的A，B矿总量尽量大。思路由题意可知，如果格子（i ，j）上选择运输A矿的话，那么i行的1~j就要全部选择A矿。同理，如果选择B矿，那么第j列上的1～ i行要全部选择B矿所以推出下面的状态转移方程式：f[i][j...

算法：uva 1407 Caves （树形背包dp）

2016年07月27日 37 阅读

算法：uva 1407 Caves （树形背包dp）2014-01-05 csdn shuangde800题意一棵n个节点的树,树的边有正整数权,表示两个节点之间的距离.你的任务是回答这样的询问:从跟 节点出发,走不超过x单位的距离,最多能经过多少节点？同一个节点经过多次, 只能算一个.思路这题同样是多天前看的, 在今天才想出解法的. 动态规划就是这么有意思 :）遍历n个节点, 有两种情 况, 第一种是遍历完之后不回到出发点, 第二种是要回到出发点.两种都...

算法：uva 1456 - Cellular Network （贪心+概率+dp）

2016年07月27日 39 阅读

算法：uva 1456 - Cellular Network （贪心+概率+dp）2014-01-05 csdn shuangde800题意（摘自LRJ《训练指南》）手机在蜂窝网络中的定位是一个基本问题。假设蜂窝网络已经得知手机处于c1, c2,…,cn这些区域中的一个，最简单的方法是同时在这些区域中寻找手机。但这样做很浪费带宽。由于蜂窝网络中可以得知手机在这不同区域中的概率，因此一个折中的方法就是把这些区域分成w组，然后依次访问。比如，已知手机可能位于5...

算法：zoj 3201 Tree of Tree（树形背包dp）

2016年07月27日 36 阅读

算法：zoj 3201 Tree of Tree（树形背包dp）2014-01-05 csdn shuangde800题意给一棵节点带权的树，找到一个有k个节点的子树，求这个子树的最大权值思路树形 dp+背包。f（i, j） 表示以i为根节点的有j个节点子树的最大权值然后对i的每个子节点做分组背包， 因为对于i的每个儿子，可以选择分配1,2,3...j-1个节点给它f（i, j） = max{ max{f（i, j-p） + f（v, p） | 1<...

算法：uva 10003 Cutting Sticks （区间dp）

2016年07月27日 38 阅读

算法：uva 10003 Cutting Sticks （区间dp）2014-01-05 csdn shuangde800题目大意一根长为l的木棍，上面有n个"切点"，每个点的位置为c[i]要按照一定顺 序把每个点都砍段，最后变成了n+1段每砍一次，就会有一个花费，例如长度为10,“切点”为2,那么砍完 后会变成两段2,8, 那么花费为2+8=10如果有多个“切点”，那么不同顺序切会得到不...

算法：zoj-3626 Treasure Hunt I （树形dp）

2016年07月27日 40 阅读

算法：zoj-3626 Treasure Hunt I （树形dp）2014-01-05 csdn shuangde800题意给一棵n个节点的树, 节点编号1~n, 每个节点有权值val[i],经过这个节点就可以获取这个价值（ 不能重复获得）每一条边有一个花费值w（i,j）, 表示走完i和j点的边要花费w（i,j）现在要从k点出发， 总花费值为m，问总花费不超过m的情况下并且最终要回到出发点，最多可以获取多少价值？思路简单树形dp。f（i,j）表示子树i,...

算法：UVA 10163 - Storage Keepers（dp）

2016年07月27日 36 阅读

算法：UVA 10163 - Storage Keepers（dp）2014-01-05 csdn shuangde800题意有n个仓库，让m个人来看管。一个仓库只能由一个人来看管，一个人可以看管多个仓库。每个人有一个能力值pi，如果他看管k个仓库，那么所看管的每个仓库的安全值为 pi/k（向下取整）如果某个仓库没有人看管，那么它的安全值为0。所有仓库的安全值L = min{ 每个仓库的安全值 }如果雇佣一个人的工资等于他的能力值pi。从m个人中选择一些人...

UVA 10254 - The Priest Mathematician （dp | 汉诺塔 | 找规律 | 大数）

2016年07月27日 32 阅读

UVA 10254 - The Priest Mathematician （dp | 汉诺塔 | 找规律 | 大数）2014-01-05 csdn shuangde800题意：汉诺塔游戏请看 百度百科：http://baike.baidu.com/view/191666.htm正常的汉诺塔游戏是只有3个柱子，并且如果有n个圆盘，至少需要2^n-1步才能达到目标。但是在 这题中，有4根柱子，并且按照下面规则来玩：1. 先把圆盘顶部前k个盘子全部搬到第四根柱子...