# 111qqz的小窝

hdu1864题目链接

## 3407: [Usaco2009 Oct]Bessie’s Weight Problem 贝茜的体重问题

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 88  Solved: 79
[Submit][Status][Discuss]

56 4
15
19
20
21

56

## BZOJ 1649: [Usaco2006 Dec]Cow Roller Coaster (dp，类似01背包)

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 <= L <= 1,000). The roller coaster comprises a collection of some of the N (1 <= N <= 10,000) different interchangable components. Each component i has a fixed length Wi (1 <= Wi <= L). Due to varying terrain, each component i can be only built starting at location Xi (0 <= Xi <= L-Wi). The cows want to string together various roller coaster components starting at 0 and ending at L so that the end of each component (except the last) is the start of the next component. Each component i has a “fun rating” Fi (1 <= Fi <= 1,000,000) and a cost Ci (1 <= Ci <= 1000). The total fun of the roller coster is the sum of the fun from each component used; the total cost is likewise the sum of the costs of each component used. The cows’ total budget is B (1 <= B <= 1000). Help the cows determine the most fun roller coaster that they can build with their budget.

## Input

* Line 1: Three space-separated integers: L, N and B.

* Lines 2..N+1: Line i+1 contains four space-separated integers, respectively: Xi, Wi, Fi, and Ci.

第1行输入L，N，B，接下来N行，每行四个整数Xi，wi，Fi，Ci．

## Output

* Line 1: A single integer that is the maximum fun value that a roller-coaster can have while staying within the budget and meeting all the other constraints. If it is not possible to build a roller-coaster within budget, output -1.

5 6 10
0 2 20 6
2 3 5 6
0 1 2 1
1 1 1 3
1 2 5 4
3 2 10 2

## Sample Output

17

dp[i][j]表示长度为i，成本为j的最大有趣指数。

bzoj1649题解

# Big Event in HDU

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 Computer College and Software College in 2002.
The splitting is absolutely a big event in HDU! At the same time, it is a trouble thing too. All facilities must go halves. First, all facilities are assessed, and two facilities are thought to be same if they have the same value. It is assumed that there is N (0<N<1000) kinds of facilities (different value, different kinds).

Input
Input contains multiple test cases. Each test case starts with a number N (0 < N <= 50 — the total number of different facilities). The next N lines contain an integer V (0<V<=50 –value of facility) and an integer M (0<M<=100 –corresponding number of the facilities) each. You can assume that all V are different.
A test case starting with a negative integer terminates input and this test case is not to be processed.

Output
For each case, print one line containing two integers A and B which denote the value of Computer College and Software College will get respectively. A and B should be as equal as possible. At the same time, you should guarantee that A is not less than B.

Sample Input
2
10 1
20 1
3
10 1
20 2
30 1
-1

Sample Output
20 10
40 40

Author
lcy

# 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个学校中选择若干的（当然要在他的经济承受范围内）。每个学校都有不同的申请费用a（万美元），并且Speakless估计了他得到这个学校offer的可能性b。不同学校之间是否得到offer不会互相影响。“I NEED A OFFER”，他大叫一声。帮帮这个可怜的人吧，帮助他计算一下，他可以收到至少一份offer的最大概率。（如果Speakless选择了多个学校，得到任意一个学校的offer都可以）。

Input

Output

Sample Input
10 3
4 0.1
4 0.2
5 0.3
0 0

Sample Output

44.0%

Hint

You should use printf(“%%”) to print a ‘%’.

Author
Speakless

Source

Recommend
JGShining   |   We have carefully selected several similar problems for you:  1171 2159 2955 1176 1114
01背包

# 饭卡

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 14225    Accepted Submission(s): 4945

Problem Description

Input

Output

Sample Input
1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0

Sample Output
-45
32

Source