题目链接 题意:容量为V的背包，n个骨头，给出价值和体积，问最多能装多少价值的背包。 思路：01背包裸体。 /* *********************************************** Author :111qqz Created Time :2016年11月16日 星期三 15时14分36秒 File Name :code/hdu/2602.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> …

hdu1864题目链接 题意：中文题目，不多说了。 思路：正解是01背包，呵呵呵。 出题人是傻逼吗？ 不给数据范围？ 以及，正解的01背包基于所有的发票额度的只有2位小数。这是让人猜？ 本来看到这题这么恶心时不打算写的... 写了的原因纯粹是为了吐槽傻逼出题人.. 简直是我做得最垃圾的题目之一。 /* *********************************************** Author :111qqz Created Time :2016年11月16日 星期三 14时13分28秒 File Name :code/hdu/1864.cpp …

题目链接 题意： 给出n个银行 ，以及抢劫每个银行可以得到的价值和被抓的概率，不同银行之间被抓的概率是相互独立的，现在给出安全概率p，只有当概率从小于安全概率时才是安全的，问最多能抢劫多少价值。 思路：一开始很直接就想到把概率算成容量， 于是就成了经典的01背包，然后发现概率是double型。。。想当然得以为最多是2位小数，于是都*100转化成了整数做01背包。 然而正确思路是，把银行价值看成背包容量，而背包价值是概率！ 将危险的概率转化成安全概率（1-危险概率=安全概率) 然后做01背包。 然后从大到小扫一遍价值，第一个大于安全概率的就是答案。 注意精度。 /* …

3407: [Usaco2009 Oct]Bessie's Weight Problem 贝茜的体重问题 Time Limit: 3 Sec Memory Limit: 128 MB Submit: 88 Solved: 79 [Submit][Status][Discuss] Description 贝茜像她的诸多姊妹一样，因为从约翰的草地吃了太多美味的草而长出了太多的赘肉．所以约翰将她置于一个及其严格的节食计划之中．她每天不能吃多过H(5≤日≤45000)公斤的干草．贝茜只能吃一整捆干草；当她开始吃一捆干草的之后就再也停不下来了．她有一个完整 的N(1≤N≤500)捆可以给她当作晚餐的干草的清单．她自然想要尽量吃到更多的干草．很 …

Time Limit: 5 Sec Memory Limit: 64 MB Submit: 504 Solved: 265 [Submit][Status][Discuss] Description The cows are building a roller coaster! They want your help to design as fun a roller coaster as possible, while keeping to the budget. The roller coaster will be built on a long linear stretch of land of length L (1 …

背包还是理解的不够透彻．． 因为每次都是用那个一维形式的． 这道题的做法类似01背包. 此外还可以有一个优化... 当n>m的时候．．．根绝抽屉原理．．一定为yes.. 复杂度可以从o(nm)优到　o(m^2) /************************************************************************* > File Name: code/cf/#319/B.cpp > Author: 111qqz > Email: rkz2013@126.com > Created Time: 2015年09月15日 星期二 19时54分44 …

**Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 26534 Accepted Submission(s): 9332 ** 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 …

I NEED A OFFER! **Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 18287 Accepted Submission(s): 7320 ** Problem Description Speakless很早就想出国，现在他已经考完了所有需要的考试，准备了所有要准备的材料，于是，便需要去申请学校了。要申请国外的任何大学，你都要交纳一定的申请费用，这可是很惊人的。Speakless没有多少钱，总共只攒了n万美元。他将在m个学校中选择若干的（当然要在他的经济承受范围 …

饭卡 **Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 14225 Accepted Submission(s): 4945 ** Problem Description 电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。 某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最 …