算法：uva 10453 - Make Palindrome （区间dp，记忆化搜索）

2016年07月27日 37 阅读

算法：uva 10453 - Make Palindrome （区间dp，记忆化搜索）2014-01-05题目大意给一个字符串，要求添加最少个字符，把它变成回文串，并输出。思路简单的区间dp,f（i, j） 表示区间（i, j） 内的字符串添加的最少个数，变成回文串那么, 如果 str[i]==str[j], f（i, j） = f（i+1, j-1） + 1f（i, j） = min{f（i+1, j）, f（i, j-1）} + 1;题目要输 出方案，...

uva 10599 - Robots（II） （dp | 记忆化搜索）

2016年07月27日 37 阅读

uva 10599 - Robots（II） （dp | 记忆化搜索）2014-01-05题意给一个n*m大小的网格，有一些格子上面会有一个垃圾。机器人从左上角（1,1）出发，每次只能选 择向右，或者向下走一步，终点是（n, m）。问最多可以捡多少个垃圾？ 且捡最多垃圾有几种路径方案？ 注意路径方案指和有垃圾的格子有关。思路一开始没注意到方案只和有垃圾的格子有关，当作水 题做，结果输出的方案数比样例大了非常多。然后又想了下。根据题意，路径只和有垃圾的格子有...

算法：uva 10859 Placing Lampposts （树形dp）

2016年07月27日 37 阅读

算法：uva 10859 Placing Lampposts （树形dp）2014-01-05 csdn shuangde题目大意给你一个ｎ个点ｍ条边的无向无环图，在尽量少的节点上放灯，使得所有边都被照亮。 每盏灯将照亮以它为一个端点的所有边。在灯的总数最小的前提下，被两盏灯同时被照亮的边数应该 尽量大。思路这是LRJ《训练指南》上的例题。这题教会了我一个很有用的技巧：有 两个所求的值要优化，比如让a尽量小，ｂ也尽量小那么可以转化为让 M*a+b尽量小，其...

算法：uva - 10271 - Chopsticks （dp | 经典）

2016年07月27日 35 阅读

算法：uva - 10271 - Chopsticks （dp | 经典）2014-01-05 csdn shuangde题意刘汝佳请了K个客人到他家吃晚饭，加上他的家人：他的老婆、儿子、女儿、妈妈、爸爸、岳父、岳母，那么这顿晚饭一共有K+8个人。因为是吃中餐，所以需要筷子，他家里一共有N根筷子，而且长短不一，这时刘汝佳的ACMer本性又暴露出来了，他不按照正常的每个人都给两只筷子，而是每个人分3根筷子，其中最长的一根用来叉比较大块的食物，而另外两根较短的...

算法：uva 12260 - Free Goodies （dp，贪心 | 好题）

2016年07月27日 37 阅读

算法：uva 12260 - Free Goodies （dp，贪心 | 好题）2014-01-05 csdn shuangde题意Petra和Jan分n个糖果，每个人轮流拿，一次只能拿一个，抽签决定谁先开始拿每个糖果 有两个值x,y, 如果Petra拿了会获得值x, Jan拿了会获得值yPetra每次都选择对自己价值最大的（x最大） 拿，如果有多个x相同大，选择y值最小的Jan选择的策略是，要让自己最终获得的总价值最大, 并且在这 个的前提下，要让Pet...

算法：uva 10934 Dropping water balloons（dp | 难想）

2016年07月27日 39 阅读

算法：uva 10934 Dropping water balloons（dp | 难想）2014-01-05 csdn shuangde题意你有k个一模一样的水球，在一个n层楼的建筑物上进行测试，你想知道水球最低从几层楼往 下丢可以让水球破掉。由于你很懒，所以你想要丢最少次水球来测出水球刚好破掉的最低楼层。（在最糟情 况下，水球在顶楼也不会破）你可以在某一层楼丢下水球来测试，如果水球没破，你可以再捡起来继续用。Input输入的每一行包含多组测试，每组测试...

算法：uva 11404 Palindromic Subsequence（LCS回文串，最小字典序）

2016年07月27日 40 阅读

算法：uva 11404 Palindromic Subsequence（LCS回文串，最小字典序）2014-01-05 csdn shuangde800题目大意给一个字符串，输出它的最长回文串，如果有多个结果，输出字典序最小的。思 路我们都知道把一个字符串逆序后和原字符串进最长公共子序列，可以计算出它的最长回文串长度。但是这题不仅要输出回文串，而且还要求是字典序最小的，所以挺难搞的。设str1是正序字符串， str2是逆序后的字符串f[i][j].len...

算法：uva 11456 - Trainsorting（dp，LIS）

2016年07月27日 41 阅读

算法：uva 11456 - Trainsorting（dp，LIS）2014-01-05 csdn shuangde800题意艾琳是个开火车的机师，她也负责车厢的调度。她喜欢把车厢依重量由大到小排列，把最重 的车厢摆在火车的前方。不幸的是，排列车厢并不容易。你不能直接把一截车厢拿起来放在别处。把一截 车箱插入现有的列车中间并不切实际。一截车厢仅能接在列车的前面或后面。车厢以事先排定的顺序抵达 车站。当一截车厢抵达时，艾琳可以把它接在列车的前方或后方，或根...

算法：uva 11552 - Fewest Flops （ 多维dp ）

2016年07月27日 40 阅读

算法：uva 11552 - Fewest Flops （ 多维dp ）2014-01-05 csdn shuangde800题意给一个字符串，把它分为ｋ块，例如字符串“helloworld”分成2块，"hello", "world"每一块里面的字母可以任意的排序。最终字符串， 连续的一样的字母算 作一个chunk，问总chunks最少是多少？思路f[i][j]: 第i块的第j位排在最后一位的...

算法：HDU 2126 Buy the souvenirs （dp 二维01背包）

2016年07月27日 40 阅读

算法：HDU 2126 Buy the souvenirs （dp 二维01背包）2014-01-07 csdn shuangde800题目大意：有n（0<n<=30）件物品，每件物品的价格是Pi，要用m（0<=m<=500）块钱去 买这些物品，要求买尽量多数量的物品，问买最多数量的物品共有多少总方案？思路：这题 还是比较容易想到的f[i][j][k], 表示前i个物品，用费用j，买k个物品共有多少个方案得到 状态转移方程：f[i]...

算法：hdu 2639 Bone Collector II （dp 01背包求第k优解）

2016年07月27日 38 阅读

算法：hdu 2639 Bone Collector II （dp 01背包求第k优解）2014-01-07 csdn shuangde800题目大意：有n件物品，每件物品有体积和价值两个属性， 一个小偷带着一个大小为v的背包，要 偷这些东西，问小偷能偷的第k大的价值是多少？思路：这题和典型的01背包求最优解不同， 是要求第k大的解，所以，最直观的想法就是在01背包的基础上再增加一维，用来保存前k大小的数，然后在 递推时，根据前一个状态的前k大小的数推出下...

算法：HDU 3062 Party （2-SAT入门学习）

2016年07月27日 36 阅读

算法：HDU 3062 Party （2-SAT入门学习）2014-01-07 csdn shuangde800Problem Description有n对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有1人可以 列席。在2n 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的2个人是不会同 时出现在聚会上的。有没有可能会有n 个人同时列席？Inputn： 表示有n对夫妻被邀请 （n<= 1000） m： 表示有m 对矛盾关...

算法：HDU 3622 Bomb Game（2-SAT + 二分）

2016年07月27日 32 阅读

算法：HDU 3622 Bomb Game（2-SAT + 二分）2014-01-07 csdn shuangde800【题目大意】要在坐标轴上放N次炸弹，每次可以选择两个位置中的一个位置放置，每个炸弹都可 以控制它的爆炸范围（以放置位置为圆心的半径为r的圆圈），问半径最大可以多少，使得任意两个炸弹的爆 炸范围都不重合。【思路】类似与poj 2296 ， 但是判断重合的方法容易多了，果断 1Y注意精度问题。【代码】#include<iostream&...

算法：HDU 3715 Go Deeper（2-SAT + 二分）

2016年07月27日 36 阅读

算法：HDU 3715 Go Deeper（2-SAT + 二分）2014-01-07 csdn shuangde800【题目大意】有一个递归代码：go（int dep, int n, int m）begin output the value of dep.if dep < m and x[a[dep]] + x[b[dep]] ！= c[dep] then go（dep + 1, n, m）end关键是看第四行， 如果满足条件dep < m...

算法：HDU 4115 Eliminate the Conflict （2-SAT判断）

2016年07月27日 40 阅读

算法：HDU 4115 Eliminate the Conflict （2-SAT判断）2014-01-07 csdn shuangde800【题目大意】Bob和Alice玩剪刀石头布，一个玩n轮，Alice已经知道了Bob每次要出什么，1代表 剪刀，2代表石头，3代表布，然后Bob对Alice作出了一些限制：给m行，每行是a b k，如果k是0，表 示Alice第a次和b次出的拳必须相同，如果k是1，表示Alice第a次和b次出的拳必须不相同。一但 Al...

算法：hdu 4558 剑侠情缘（dp， 西山居复赛1第2题）

2016年07月27日 36 阅读

算法：hdu 4558 剑侠情缘（dp， 西山居复赛1第2题）2014-01-10 csdn shuangde800思路：这是刚练dp后做比赛遇到的第一道dp题比赛时想了一个状态转移方程，f[i][j][k][l][2], i和j表示在第i行j列， k和l表示人和剑的能量，最后一维0表示当前这个能量给人补充，1表示给剑补充转移为： f[i][j][k][l][0] = f[i-1][j][k-mat[i][j]][l][1]+f[i][j-1][k-mat...

算法：poj 1837 Balance （dp 01背包）

2016年07月27日 36 阅读

算法：poj 1837 Balance （dp 01背包）2014-01-10 csdn shuangde800题目大意：有一个天平，天平左右两边的手臂长度都是15，手臂上面有些位置会有挂钩。还有G 个砝码 （1 <= G <= 20），它们重量各不相同，在1~25中取值。给出C个挂钩，它们的位置在 【-15..15】，不会重叠。负号的代表在左边臂，正号的在右边。要求把所有砝码都放在挂钩上，多 个砝码可以挂在同一个挂钩上，问有多少种不同的方案使...

算法：poj 1948 Triangular Pastures （dp 二维01背包）

2016年07月27日 45 阅读

算法：poj 1948 Triangular Pastures （dp 二维01背包）2014-01-10 csdn shuangde800题目大意：给N条边，把这些边组成一个三角形，问面积最大是多少？必须把所有边都用上。思路：对于已知周长的三角形，我们只要知道两条边的长度变可推出第三条边，所以可以得 到状态方程：f[i][j][k] 表示用前i条边，能否组成长度为j和k的两条边初始化f[0][0][0] = true；f[i][j][k] = f[i-1...

算法：poj 1976 A Mini Locomotive （dp 二维01背包）

2016年07月27日 35 阅读

算法：poj 1976 A Mini Locomotive （dp 二维01背包）2014-01-10 csdn shuangde800题目大意：某个车站有N个火车车厢，编号为1～N，每个车厢上有xi个人。这个车站还有 三个火车头，他们能拉最多m个车厢（m<=N/3），而且这m个车厢的编号要连续的。问这三个火车头最多 能拉多少个人。思路：因为m<=N/3， 所以按照贪心的思想，为了拉更多的人，每个火车 头一定是要拉m个连续的车厢。然后，为了求某...

算法：poj 2063 Investment （dp 完全背包）

2016年07月27日 37 阅读

算法：poj 2063 Investment （dp 完全背包）2014-01-10 csdn shuangde800题目大意：有n种债券可以买，每种的价钱分别为a（a是1000的倍数），每年利息为b 。某个人 共有钱tot（tot是1000的倍数），问他在y年后，最多可以有多少钱？思路：由于tot和a都 是 1000的倍数，所有在计算时可以把他们缩小1000倍，这样节约内存和时间。按照贪心的思想，每 一年都用完全背包求出这一年最大可以得到的利息，然后下一...