- 博客(13)
- 收藏
- 关注
RSS订阅原创 无向图的最小边覆盖
边覆盖的定义：无向图G(V,E)边覆盖的求解步骤：1.将无向图拆点，即若在无向图中存在节点i，则将节点i拆为i1,i2分别位于二分图的X部和Y部.若存在边ij，则连接二分图的i1j2,i2j1。2.原无向图中的节点数为|V|所以在构造的二分图有2*|V|个节点。在二分图中存在公式：2*|V| = 2*二分图的最大匹配数 + 二分图中未匹配的点。其中二分图的最大匹
2013-04-12 09:01:00
2279
1
原创 最长递增子序列（LIS）的两种实现
最长递增子序列（LIS）1.最长递增子序列的问题描述给定一序列L=(a1,a2,a3,a4......an-1,an),存在序列L'=(ai1,ai2,ai3......aik)满足ai12.有两种算法解决方法(1).用一个序列L1保存L排序后的结果，然后找L1和L的最长公共子序列。（在这里不涉及，主要讲方法二的两个实现）方法(2).动态规划实现。由于简单递推公式直接给出。op
2013-04-09 09:38:47
509
原创 POJ 3292.Semi-prime H-numbers
题目链接：http://poj.org/problem?id=3292题目大意：H数即5,9,13,17,21.......4*n+1；若一个H数可以分解为两个H数相乘则H数为H合数，否则称为H质数，若一个H数可以分解为两个H质数的成绩则称之为Semi-prime H.求在给定的书n，在[1,n]里面有多少个Semi-prime H。解题思路：水题一个直接上代码，用到了类似求10^6以内所
2013-04-02 14:54:56
977
原创 HDU 4526.威威猫系列故事——拼车记
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4526解题思路：用动态规划既可以解决。opt[i,j]代表在[t(1),t(2),......t(i)]时刻内走j个人所需的最小花费。显然地推关系式如下： opt[i,j] = min (opt[i-1][j], opt[i-1,j-k]+k*t(i)+d);(其中k代表t(i)时刻上车的人
2013-04-02 09:24:36
757
原创 POJ 1321.棋盘问题
题目链接：http://poj.org/problem?id=1321简单的水题一个直接dfs搞定，代码如下：#include #include using namespace std;int n, k;char data[8][8];int ans;int visited[8];void dfs(int cur, int count){ if (cur >= n)
2013-04-01 17:58:55
396
原创 POJ 3295.Tautology
题目链接：http://poj.org/problem?id=3295题目大意：一个逻辑表达式，最多有五个输入人，p，q，r，s，t。有五种操作，判断是不是对于任意输入输出都为1.解题思路：应为输入只有5个，且输入只能为0,1。所以最多就只有32种情况，有表达式最多100个字符也不多。直接暴力求解即可。用堆栈求解表达式，从表达式从最后开始，如果是p，q，r，s，t压入堆栈，如果是K、A、N
2013-03-30 00:23:54
681
原创 POJ 2104.K-th Number
题目链接：http://poj.org/problem?id=2104题目大意：给定一个数组p[1,2,3.....n]，然后给定(i,j,k)，查询数组区间为[i,j]的第k小的数。解题思路：用struct保存数组中每个数的大小和原始数组的序号。struct s_Node{ int num; int data; bool operator < (const s_Node&
2013-03-30 00:16:45
615
原创 POJ 2586.Y2K Accounting Bug
题目链接：http://poj.org/problem?id=2586题目大意：水题一个，但是半天读不懂题目比较恼火。题目的意思是该公司每个月不是亏损d就是盈利s，d和s的值每个月都是一样的。现在公司只知道每个连续的五个月的和都是亏损。求一年下来公司最多盈利多少?解题思路：由于只有一年只有12个月，要想盈利最多就必须是盈利的月份越多越好，当然要满足连续的五个月必须亏损的
2013-03-29 15:01:36
817
原创 POJ 1328.Radar Installation
题目链接：http://poj.org/problem?id=1328题目：Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And
2013-03-27 23:17:20
409
原创 POJ 2109.Power of Cryptography
题目链接：http://poj.org/problem?id=2109题目大意：等式 kn = p，题目给出n和p，求底数k。（1101 ， 19)解题思路： 一开始被10101给唬住了以为要用大整数乘法，后来百度double的数据范围负值取值范围为 -1.79769313486231570E+308 到 -4.94065645841246544E-324，正值取值范围为 4.94
2013-03-27 21:11:14
442
原创 POJ 1753.Flip Game
题目链接：http://poj.org/problem?id=1753题目直接暴力求解即可，方法与POJ2965 一样点击打开链接代码改动很小#include #include using namespace std;int data;int operate[16];void set(int &data,int pos,int flag){ if (flag
2013-03-27 13:03:37
404
原创 POJ 2965.The Pilots Brothers' refrigerator
题目连接：http://poj.org/problem?id=2965题目大意：一个4*4的矩阵，标号为'+'或'-'，当标号全为'-'时就算达到目的。一次操作可以改变‘+’为‘-’，或是‘-’为‘+’。（即符号改变）但是对于坐标[i，j]的改变将会同样施加到i行和j列。要求得出最小操作次数，以及有哪些操作，给出最小操作的坐标，有多个答案输出一周即可。解题思路： 直接暴力求解，用0--
2013-03-27 12:41:02
521
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人