链接：   文章目录    题目描述 题解： 代码:    题目描述  Applese有1个容量为v的背包，有n个物品，每一个物品有一个价值ai，以及一个大小bi 然后他对此提出了自己的疑问，如果我不要装的物品装的价值最大，只是一定需要装m个物品，要使得求出来的物品价值的中位数最大 Applese觉得这个题依然太菜，于是他把这个问题丢给了你 当物品数量为偶数时，中位数即中间两个物品的价值的平均值  输入描述:  第一行三个数v, n, m，分别代表背包容量，物品数量以及需要取出的物品数量 接下来n行，每行两个数ai，bi，分别代表物品价值以及大小 n ≤ 1e5, 1 ≤ m ≤ n, ai ...

链接：   文章目录    题目描述    题目描述  这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。 注意：选出的k个子矩阵 不能相互重叠。  输入描述:  第一行为n,m,k（1 ≤ n ≤ 100,1 ≤ m ≤ 2,1 ≤ k ≤ 10）， 接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。  输出描述:  只有一行为k个子矩阵分值之和最大为多少。  示例1 输入 3 2 2 1 -3 2 3 -2 3  输出 9  题解： m的范围是1~2 当m=1时，就相当于一维数组，求最大连续k段和 dp[i][j]表示前i个位...

背包问题大汇总  文章目录    背包问题大汇总 01背包   问题： 思路： 空间优化复杂度 代码  完全背包   问题： 思路： 代码： 优化  多重背包   问题： 思路： 代码： 单调队列优化  混合三种背包   问题： 思路 例题 代码：  二维费用的背包问题 分组的背包问题 有依赖的背包问题 背包问题的方案总数    01背包 问题：  有Ｎ件物品和一个容量为Ｖ的背包，第ｉ件物品的费用（体积）是ｗ［ｉ］，价值是ｃ［ｉ],求解将哪些物品装入背包可使这些物品的费用综合不超过背包容量，且价值总和最大  思路： f[i][v]表示前i件物品（部分或全部）恰放入一个容量为v的背包可以获得的最...

HDU链接   文章目录    题目描述： 题意： 题解 （代码）    题目描述：  输入描述:  输出描述:  For each test case output the answer on a single line.  输入 3 10 1 2 4 2 1 1 2 5 1 4 2 1 0 0  输出 8 4  题意： 有n种硬币，面额分别是Ai，每种硬币数量分别是Ci，问这些硬币能组成1~m中多少个数？ 样例分析： 3 10 1 2 4 2 1 1 有2个一元，1个两元，1个四元，可以组成1,2，3，4,5，6，7,8，（9和10无法组成）能组成的一共八个 题解 如果还没学习背包问题的知...

Hdu链接   文章目录    题目描述 题意： 题解： 代码：    题目描述  输入描述:  输出描述:  示例1 输入 1 0 1 2 0 0 1 0 0 0 1 1 0 0 0 0 0 0  输出 Collection #1: Can't be divided. Collection #2: Can be divided.  题意： 有价值分别是1~6的6种大理石，每种大理石的数量是ni，问能否将这些大理石分成完全相同的两部分？ 题解： 这个题和hdu 2844 Coins做法基本一样，不过本题要稍微转变下思路 我们考虑用背包方法来做，题目给了数量，价值，却没有给总容量和体积。我们结合...

hdu试题链接   文章目录    Problem Description 题意： 题解： 代码：    Problem Description  Nowadays, we all know that Computer College is the biggest department in HDU. But, maybe you don’t know that Computer College had ever been split into Computer College and Software College in 2002. The splitting is absolutely ...

文章目录    Problem Description 题意： 题解： 代码：     hdu-1114 Problem Description  Before ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action comes from Irreversibly Bound Money (IBM). The idea behind is simple. Whenever some ACM member...

牛客网   文章目录    题目描述 题解： 代码：    题目描述  Rabbit通过了上次boss的考核，现在她又遇到了一个问题。 Rabbit接到了K个任务，每个任务她可以自由选择用i天去完成(1≤ i≤ N)。刁钻的boss想让Rabbit恰好用W天完成所有任务。 已知Rabbit用i天完成一个任务能让boss获得的满意度为vi(因为完成任务的质量不同)，她想知道在满足boss要求的情况下能让boss获得的总满意度最大是多少。  输入描述: 第一行三个整数N，K，W。 第二行N个整数vi，vi表示用i天完成一个任务能让boss获得的满意度。 输出描述: 输出Rabbit在满足boss要...

来源：牛客网  文章目录    题目描述 题解： 代码：    题目描述  xinjun是各类手游的狂热粉丝，因随手一氪、一氪上千而威震工大，现在他迷上了阴阳师。xinjun玩手游有一个习惯，就是经过层层计算制定出一套方案来使操作利益最大化(因此即使有扫荡券也不用，故称圣雄肝帝)。已知阴阳师有N个模式可以操作，模式i有ai种操作，但每种模式每日只能选用一种操作，可以不选。操作j能收益vj，但需要花费体力wj点。xinjun每日拥有体力M点，求他每日最多能得到多少收益。  输入描述:  第一行一个正整数T(T<=10)，表示共有T组数据。 对于每组数据，第一行两个正整数N，M(1<=...

牛客网 poj 2553   文章目录    Description 题意： 题解： 代码：    Description  We will use the following (standard) definitions from graph theory. Let V be a nonempty and finite set, its elements being called vertices (or nodes). Let E be a subset of the Cartesian product V×V, its elements being called edges. Then ...

HDU1269 迷宫城堡   文章目录    Problem Description 题解：    Problem Description 为了训练小希的方向感，Gardon建立了一座大城堡，里面有N个房间(N<=10000)和M条通道(M<=100000)，每个通道都是单向的，就是说若称某通道连通了A房间和B房间，只说明可以通过这个通道由A房间到达B房间，但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的，即：对于任意的i和j，至少存在一条路径可以从房间i到房间j，也存在一条路径可以从房间j到房间i。 Input 输入包含多...

POJ1236 Network of Schools   文章目录    Description 题意： 题解： 代码：    Description  A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the “receiving schools”). Note that if B...

POJ3177 Redundant Paths   文章目录    Description 题意： 题解： 代码：    Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 21945 Accepted: 9056  Description  In order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numbered 1…F) to another field, Bessie and the rest of the he...

Network POJ-3694   文章目录    Description 题意： 样例分析： 题解： 代码：    Description  A network administrator manages a large network. The network consists of N computers and M links between pairs of computers. Any pair of computers are connected directly or indirectly by successive links, so data can be transfo...