夜祈-CSDN博客

原创棋盘型动态规划

棋盘型动态规划，一般指在二维平面上进行操作的一种DP。这种问题一般是根据可能达到当前状态的所有情况作出最优判断。这种最优判断可能是上一层之和也可能是上一层的最优值。这种问题没有固定的模板，一般是从一个点到另一个点，中间加点限制的东西，所求问题可能是路径数或者是某条路径的最大权值。codevs-1010 过河卒如图，A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右

2015-05-03 17:38:43 1887

原创序列型动态规划

区间型动态规划主要分为两种：最长公共子系列（LCS）和最长上升子序列（LIS）。最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。而最长公共子串(要求连续)和最长公共子序列是不同的。//最长公共子序列模板#i

2015-05-03 16:51:40 691

原创二叉树的序遍历

先说一下最基本的概念：前序遍历：根->左孩子->右孩子。中序遍历：左孩子->根->右孩子。后序遍历：左孩子->右孩子->根。然后是二叉树的存储方式。这里用的是用数组存储二叉树。先开一个tree[]数组，tree[1]为二叉树的根节点，非零表示存在该节点，反之不存在。对于tree[i]，它的左孩子为tree[2*i]，右孩子为tree[2*i+1]。下面祭上三

2015-04-11 15:17:36 341

原创单词翻转

#include #include #include using namespace std;vector ve;string strcut(string &str);int main(){ string str; getline(cin, str); while(str.size()) { ve.push_back(strcut(st

2015-04-08 21:44:52 324

原创限定条件不止一种的背包问题

对于正常的背包问题，只有一个限定条件——背包容量不超过多少，而有些背包问题有多重限定条件，比如NASA的食物计划这道题，有体积和质量这两个限定条件。对于这种问题，其实是和正常的背包问题是差不多的，只需要多加一层循环而已。下面附上这道题的代码：#include #include #define MAXL 401using namespace std;int dp[MAXL][M

2015-03-14 09:45:42 4042

原创最小公约数和最大公倍数模板

int gcd(int m,int n)//最大公约数，辗转相除法{ do { r=m%n; m=n; n=r; } while(n); return m;}------------------------------------------------int gcd(int m,

2015-03-14 09:26:02 324

原创浅谈分组背包

分组背包，由基础背包演化而来的一种情况。具体问题是这样的。具体问题是这样的。一个容量为V的背包，还有若干组物品，每组包含若干物品，这些物品各不相同，而且体积w和价值p各不相同。组内的物品相冲突。求出能在不超过V的情况下尽可能的使价值最大。乍一看好像很难的样子，其实仔细想想很简单，这种问题完全可以用01背包解决。对于分组背包，可以这样想：虽然分成很多组，但只能选一个，或者不

2015-03-14 09:21:51 2785 1

原创浅谈多重背包

多重背包，基础背包问题之三。具体问题是这样的。一个容量为V的背包，还有一些物品（每个物品有具体的数量c），这些物品的体积w和价值p各不相同。求出能在不超过V的情况下尽可能的使价值最大。对于多重背包问题，可以根据每个物品的数量分解成两种情况：1.当c >= V / w时，相当于物品可以无限使用，即转化为完全背包求解。2.当c 但是上面这种方法的时间复杂度为

2015-03-14 09:20:55 878

原创浅谈01背包和完全背包

01背包，基础背包问题之一。具体问题是这样的。一个容量为V的背包，还有一些物品（每个物品只有一个），这些物品的体积w和价值p各不相同。求出能在不超过V的情况下尽可能的使价值最大。对于01背包问题，用动态规划的思想很简单，只需考虑子问题的两种情况：如果i个物品放入，那么就转化为前i-1个装入j-w[i],价值为dp[i-1][j-w[i]]+p[i]。如果i个物品不放

2015-03-14 09:15:40 439

原创 poj-1458 Common Subsequence

最长公共子序列（LCS）题目传送门：http://poj.org/problem?id=1458这是一道很经典的dp问题。这里先说一下子序列和字串的区别。字串是指在一个字串里连续的字符。注意这里是连续的。而子序列是指在不打乱原来字串字符的顺序的情况下，最长的可以间断的字符序列。也就是说子序列可以不连续。举个例子：a字串：aebfcghidb字串：abcdefgh

2015-01-16 15:28:18 623

原创 poj-2479 Maximum sum

题目传送门：http://poj.org/problem?id=2479此题是比较经典的动规题，left[]是从左到右的最大和，right[]是从右到左的最大和。最后左右相加判断最大值即可。详细解释：left[i]存的是从0到i的最大和，如果left[i]的值为负，那么left[i + 1]的值为a[i + 1]，否则在此基础上加上left[i]，因为如果left[i]为负的话，lef

2015-01-10 20:50:39 268

原创 ACM并查集浅谈

并查集，顾名思义，就是查找集合然后合并。主要思想就是通过find-union函数实现的，所有的元素都用一个数组表示。如果两个元素属于一个集合，就用find函数将两个元素划分到一个集合中。在ACM常见题中，主要分为两种情况：1.集合数量未知。2.集合数量已知。对于几何数量未知的情况，

2014-12-22 20:25:11 606

原创 poj-1703 find them,catch them!

Find them, Catch themTime Limit: 1000MS Memory Limit: 10000KTotal Submissions: 32636Accepted: 10073DescriptionThe police office in Tadu City decides to say ends to the chaos, as laun

2014-12-19 15:08:04 336

原创 vijos-P1531食物链

描述动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A吃B，B吃C，C吃A。现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述：第一种说法是“1 X Y”，表示X和Y是同类。第二种说法是“2 X Y”，表示X吃Y。此人对N个动物，用上述两种说法，一句接一句

2014-12-16 12:14:47 369

kyriesnow的专栏