ACM_背包问题
LzyRapX
Just For Fun .
展开
-
ACdream 1119 瑶瑶的动感光波(加强版)(LCA)(背包dp)
题目链接: ACdream 1109题意:中文题意….题解: 如果这题按照 ACdream 1102 题解 去做,肯定会TLE。我们先DFSDFS预处理出全部结点的父节点,深度所有点对的LCALCA(最近公共祖先)。枚举以每个结点开始到根结点这段路径上每一段长度上背包容量为0 ~ 50的选取情况的最优价值。对于每次询问,可以拆分成两部分,一部分是xx到zz且包括zz的一段路,即:dep[x]−d原创 2017-07-12 19:28:16 · 473 阅读 · 0 评论 -
ACdream 1102 瑶瑶的动感光波 (树形dp)(背包dp)
题目链接: ACdream 1102 题意: 自己点链接进去看吧…中文题面。。。题解: 先预处理求出每个结点的父节点,然后在这棵树上做背包 dp dp 就可以了。这题还有加强版。 题目链接: ACdream 1119 加强版题解: ACdream 1119 题解做法有点复杂。这题代码交上去完全会TLE。等等写一下加强版吧。AC代码:/** this code is made by L原创 2017-07-10 12:07:28 · 446 阅读 · 0 评论 -
B. Lorry (贪心)
点击打开链接http://codeforces.com/contest/3/problem/BB. LorryDescriptionA group of tourists is going to kayak and catamaran tour. A rented lorry has arrived to the boat depot t原创 2017-04-02 17:26:13 · 695 阅读 · 0 评论 -
金明的预算方案 (变形01背包)
问题描述 金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附件是从属于某个主件的,下表就是一些主件与附件的例子:主件附件电脑打印原创 2017-03-15 18:18:08 · 839 阅读 · 0 评论 -
Problem 31 Coin sums(完全背包dp)
Coin sumsProblem 31In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).It原创 2016-10-29 12:14:20 · 616 阅读 · 0 评论 -
hihocoder #1043 : 完全背包 (DP)
#1043 : 完全背包时间限制:20000ms单点时限:1000ms内存限制:256MB描述且说之前的故事里,小Hi和小Ho费劲心思终于拿到了茫茫多的奖券!而现在,终于到了小Ho领取奖励的时刻了!等等,这段故事为何似曾相识?这就要从平行宇宙理论说起了………总而言之,在另一个宇宙中,小Ho面临的问题发生了细微的变化!小Ho现在手上原创 2016-07-29 10:58:37 · 629 阅读 · 0 评论 -
HDU 1248 寒冰王座(完全背包)(dp 或 暴力)
寒冰王座Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 14414 Accepted Submission(s): 7369Problem Description不死族的巫妖王发工资拉,死亡骑士拿到一张N元原创 2016-04-24 19:28:56 · 700 阅读 · 0 评论 -
背包九讲
背包九讲P01: 01背包问题 题目 有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。 基本思路 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。 用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状原创 2016-03-09 23:35:34 · 1233 阅读 · 0 评论 -
小明系列故事——买年货(三重背包)
小明系列故事——买年货Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 2221 Accepted Submission(s): 995Problem Description 春节将至,小明要去超市购置年货,于是小明去了自己经常原创 2016-01-16 19:59:14 · 752 阅读 · 0 评论 -
吉哥系列故事——临时工计划
吉哥系列故事——临时工计划Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 2744 Accepted Submission(s): 1061Problem Description 俗话说一分钱难倒英雄汉,高中几年下来,吉哥已经原创 2016-01-16 19:57:03 · 779 阅读 · 0 评论 -
v字仇杀队
v字仇杀队时间限制:1 秒内存限制:32 兆特殊判题:否提交:392解决:161 题目描述: 最近玄影游侠看了一部非常好看的电影,叫做《v字仇杀队》。下面是这部电影的主角v: 它想说明的一个问题就是,你现在所想的真的是你自己内心所想的吗?还是别人,社会让你这么想的?你要有自己的想法,每个人内心都有自己的准则,你没有必要按照大众的准则去想。 v整整策划了一年炸掉原创 2016-01-16 19:47:30 · 3317 阅读 · 0 评论 -
最小邮票数
最小邮票数时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:1680 解决:558 题目描述: 有若干张邮票,要求从中选取最少的邮票张数凑成一个给定的总值。 如,有1分,3分,3分,3分,4分五张邮票,要求凑成10分,则使用3张邮票:3分、3分、4分即可。 输入: 有多组数据,对于每组数据,首先是要求凑成的邮票总值M,M100。然后是一个数N,N原创 2016-01-16 19:37:40 · 1121 阅读 · 0 评论 -
ACdream 1110 True love (多重背包+dp)
题目链接: ACdream 1110题意: 给你一些物品的体积和对应的数量,求可以拿走多少体积不一样的物品,且不超过背包的容量。题解: 多重背包呗。 dp dp 题。设 dp[i] dp[i] 表示容量为 i i 的种类数量。 那么容易得到转移方程: dp[j+a[i]]=dp[j]+1 dp[ j + a[ i ] ] = dp[j] + 1 且 j+a[i]<cap j + a[原创 2017-07-23 10:41:27 · 451 阅读 · 0 评论