算法：POJ 2184 Cow Exhibition （dp 转换01背包）

2016年07月27日 38 阅读

算法：POJ 2184 Cow Exhibition （dp 转换01背包）2014-01-10 csdn shuangde800题目大意：有N个物品，每个物品有属性Si和Fi，-1000 <= Si, Fi <= 1000, 每种物品最 多只能选一次，问怎样选使得物品的所有Si和Fi属性之和最大，并且要求Si之和与Fi之和都不能下于 0.思路：这题想了很久都没思路，于是跟前辈请教了下，恍然大悟。把属性Si当做是物品的 费用，Fi当做是价值，然...

算法：POJ 2296 Map Labeler（2-SAT+二分）

2016年07月27日 35 阅读

算法：POJ 2296 Map Labeler（2-SAT+二分）2014-01-10 csdn shuangde800【题目大意】坐标轴上有N个点，要在每个点上贴一个正方形，这个正方形的横竖边分别和x，y 轴平行，并且要使得点要么在正方形的上面那条边的中点，或者在下面那条边的中点，并且任意两个点的正 方形都不重叠（可以重边）。问正方形最大边长可以多少？【思路】可以很容易的看出，正 方形要么在点的上方，要么在下方，所以是用2-SAT来判断的，关键是加边的判...

算法：poj 2392 Space Elevator（dp 排序+多重背包）

2016年07月27日 36 阅读

算法：poj 2392 Space Elevator（dp 排序+多重背包）2014-01-10 csdn shuangde800题目大意：有n种砖头，每种砖头的高为h，数量为c， 且它放的最高位置不能超过a。 问这些砖 最高能够叠多高？思路：先把所有种类砖头按照a从大到小排序，然后直接套多重背包即可 。代码：#include<iostream>#include<queue>#include<stack>#include...

算法：poj 2642 The Brick Stops Here（01背包）

2016年07月27日 36 阅读

算法：poj 2642 The Brick Stops Here（01背包）2014-01-10 csdn shuangde800题目大意：黄铜砖是由铜和锌两种元素组成的，每一块黄铜砖中1000克，铜占其中的1～999克之 间。铜占比重不同的黄铜砖是属于不同类的。有N个黄铜砖，给出它们的铜占的重量以及价格。现在 有c个客户，每个可以要买Mi个不同类的黄铜砖，要求把Mi个黄铜砖融化后，铜站的比率为每千克在 【CMin，CMax】克之间。问每个客户最少花多少...

算法：POJ 2723 Get Luffy Out（2-SAT + 二分）

2016年07月27日 38 阅读

算法：POJ 2723 Get Luffy Out（2-SAT + 二分）2014-01-10 csdn shuangde800【题目大意】有2*N把不同的锁，每把锁有一个钥匙，所以共有2*N 把钥匙。把2*N把钥匙两两配 对共分为N组。有个M层楼，每层楼有一个门，每个门上有两把锁，可能是相同的也可能是不同的。 走上某层楼之前，必须要打开这个门上的至少一个锁。要你从每组钥匙中选择一把钥匙，然后用这 些钥匙去上这栋楼，问最多能走到几层楼？【思路】对于每组钥匙...

算法：poj 2749 &amp; hdu 1815 Building roads（2-SAT + 二分，好题）

2016年07月27日 35 阅读

算法：poj 2749 & hdu 1815 Building roads（2-SAT + 二分，好题）2014-01-10 csdn shuangde800【题目大意】有n个牛棚， 还有两个中转站S1和S2， S1和S2用一条路连接起来。 为了使得任意 牛棚两个都可以有道路联通，现在要让每个牛棚都连接一条路到S1或者S2。有a对牛棚互相有仇恨， 所以不能让他们的路连接到同一个中转站。还有b对牛棚互相喜欢，所以他们的路必须连到同一个中专站。道路的长...

算法：poj 2923 Relocation （枚举+背包 | 状态压缩+01背包）

2016年07月27日 36 阅读

算法：poj 2923 Relocation （枚举+背包 | 状态压缩+01背包）2014-01-10 csdn shuangde800题目大意：有N件家具，每件的重量为（1 ≤ wi ≤ 100）， 用两辆车把他们来运送到目的地。这 两辆车的限载重量分别为C1, C2（1 ≤ Ci ≤ 100） , 问最少几趟可以把所有家具运送到目的地。这两辆车每趟都必须一起走，即使某辆车没载东西。思路：（一）先上自己的方法：枚举第一辆车可能载...

算法：poj 3211 Washing Clothes（01背包）

2016年07月27日 38 阅读

算法：poj 3211 Washing Clothes（01背包）2014-01-10 csdn shuangde800题目大意：Dearboy和他的女朋友一起洗m件衣服，共有n总颜色（每件衣服只有一种颜色）。 为 了放置不同颜色互染，每次只能洗一种颜色的衣服，在这件衣服洗完之前不能洗另外一种衣服。 Dearboy和 他女朋友可以同时一起洗衣服，但是不能同时洗同一件衣服，也不能同时洗不同种颜色的衣服。一 只每件衣服所需时间，问最少花费多少时间可以全部洗完。...

算法：poj 3628 Bookshelf 2（dfs, 01背包）

2016年07月27日 38 阅读

算法：poj 3628 Bookshelf 2（dfs, 01背包）2014-01-10 csdn shuangde800题目大意：有n个数字（1～100W），现在有一个数b，1<=b<=s（s为n个数字之和）。要从n 个数字中选择一些数字组合，有一写组合的数字之和x会大于等于b， 求所有x中x-b最小的是多少？思路：刚开始看到这题，发现数字这么大，以为内存不够不能用背包。而n最大才20，所以直接用 dfs+减枝0MS过了。。。然后用背包，开了...

算法：POJ 3648 Wedding（2-SAT+输出方案）

2016年07月27日 41 阅读

算法：POJ 3648 Wedding（2-SAT+输出方案）2014-01-10 csdn shuangde800【题目大意】有n-1对夫妇被一对新郎新娘邀请来参加婚礼，他们要坐在一条长桌上，可以选择 坐在左边或者右边。每对夫妻都不能坐在同一边，他们只能是面对面坐着。但是这些人中有JQ，共 有m对有JQ（新郎也可能有奸情，可怜的新娘...）。要求这些JQ对不能同时坐在新娘的对面。即，每一对JQ 者，他们可以同时坐在和新娘同一边，也可以一个和新娘同一边而另...

算法：POJ 3678 Katu Puzzle（2-SAT判断）

2016年07月27日 39 阅读

算法：POJ 3678 Katu Puzzle（2-SAT判断）2014-01-10 csdn shuangde800【题目大意】有一个有向图G（V，E），每条边e（a,b）上有一个位运算符op（AND， OR或XOR） 和一个值c（0或1）。问能不能在这个图上的每个点分配一个值X（0或1），使得每一条边e（a,b）满 足 Xa op Xb = c【思路】每一个点上只能取0或者1，显然是2-SAT模型。关键是怎样建边。对于两个点a和 b， a有两个值a1...

算法：poj 3905 Perfect Election（2-SAT判断简单）

2016年07月27日 40 阅读

算法：poj 3905 Perfect Election（2-SAT判断简单）2014-01-10 csdn shuangde800【思路】2-SAT简单的判断题【代码】#include<iostream>#include<queue>#include<cstdio>#include<cstring>using namespace std;const int MAXN = 1010;const int VN ...

算法：UVa 1146 - Now or later（2-SAT + 二分）

2016年07月27日 38 阅读

算法：UVa 1146 - Now or later（2-SAT + 二分）2014-01-10 csdn shuangde800【题目大意】有n架飞机要着陆， 每架飞机都可以选择“早着陆”或者“晚着陆”中的一种，不 能在其他时间着陆。 给出每架飞机“早着陆”和“玩着陆”的时间， 问怎样安排着陆，才可以使得着任意 两架飞机的陆时间间隔最小，输出最小值。【思路】水...

算法：UVA 1391 Astronauts（2-SAT + 输出方案）

2016年07月27日 40 阅读

算法：UVA 1391 Astronauts（2-SAT + 输出方案）2014-01-10 csdn shuangde800【题目大意】有n个宇航员，按照年龄划分，年龄低于平均年龄的是年轻宇航员，而年龄大于等 于平均年龄的是老练的宇航员。现在要分配他们去A，B，C三个空间站，其中A站只有老练的宇航员 才能去，而B站是只有年轻的才能去，C站都可以去。有m对宇航员相互讨厌，不能让他们在同一个空 间站工作。输出每个宇航员应分配到哪个空间站，如果没有则输出No ...

算法：ZOJ 3656 Bit Magic （2-SAT判断）

2016年07月27日 37 阅读

算法：ZOJ 3656 Bit Magic （2-SAT判断）2014-01-10 csdn shuangde800【题目大意】假设已经知道一个数组a[N]，那么用一下函数生成一个矩阵b：void calculate（int a[N], int b[N][N]） {for （int i = 0; i < N; ++i） {for （int j = 0; j < N; ++j） { if （i == j） b[i][j] = 0; else if...

算法：ZOJ 3659 Conquer a New Region（并查集）

2016年07月27日 38 阅读

算法：ZOJ 3659 Conquer a New Region（并查集）2014-01-10 csdn shuangde800【题目大意】有N个城市，N-1条路把这些城市连起来（刚好是一个树）。相邻的两个城市有一个 运输容量C（i, j），而城市x到城市y的那条路的运输能力S取决与这条路上所经过的所有路中最小的那个容量 。 以那一个城市为中心，到其他N-1个城市的运输能力总和最大？【思路】用神奇的并查集 ，把路按照权值从大到小排序，然后用类似Kruska...

算法：UVa 12174 - Shuffle

2016年07月27日 37 阅读

算法：UVa 12174 - Shuffle2014-03-17 csdn博客 shuangde800【题目大意】你在听音乐播放器，它采用随机播放形式。随机播放的原理时先随机产生一个 1~n的排列，然后就按这个排列顺序播放歌曲。播放完这序列的所有歌曲以后，再次随机生成一个1～n的 排列，再继续播放。现在给你一个播放历史记录，这个历史记录是不完整的，以为它是开始记录 时，已经有些歌曲播放过了而没有记录到。现在给你一段从某个时刻开始的播放音乐的历史记录 ，以及...

算法：UVa 11536 - Smallest Sub-Array

2016年07月27日 34 阅读

算法：UVa 11536 - Smallest Sub-Array2014-03-17 csdn博客 shuangde800题目大意：给一个序列X1 = 1X2 = 2X3 = 3Xi = （Xi-1 + Xi-2 + Xi-3） % M + 1 for i = 4 to N求一段最短的连续子序 列，使得这个子序列包含正整数【1，k】思路：扫描一遍即可，用一个队列记录下【1， k】区间内的数的位置，再用一个变量count维护【1，k】内不重复数的个...

算法：UVa 11572 - Unique Snowflakes （好题）

2016年07月27日 44 阅读

算法：UVa 11572 - Unique Snowflakes （好题）2014-03-17 csdn博客 shuangde800题目大意：给n个数， n<=100W，求一个连续子序列，这个子序列中没有重复的数，问这个子序列最长是多少？思路：开一个数组pos， pos[ x ] 表示x出现的位置， 这个数组初始化为-1用一个变量start来记录当前枚举序列的起点，初始为0然后枚举这个序列，依次记录每个数的位置，假设当前枚举到i， 在记录这个位置之前...

算法：uva 10730 - Antiarithmetic

2016年07月27日 39 阅读

算法：uva 10730 - Antiarithmetic2014-03-17 csdn博客 shuangde800题目大意：给n个数组成的序列，他们是0~n-1， 问序列中是否有按顺序的3个数，是等差数 列。思路：用一个数组记录每个数在序列中的位置，然后枚举3个数中最小的一个，再枚 举等差数列的增量，最后看着三个数的位置是不是连续的即可。n最大为1W，但这个算法的复杂 度看起来好像是O（n^2），怎么速度还挺快的呢？粗略的分析一下复杂度吧。第一层for循...