Too Young - BuringStraw

Too Young#

Today I did a set of mock exams and scored 20.

The person who set this exam was violent throughout the entire process%, ~~the joke was good,——.~~

But as I kept laughing, I couldn't laugh anymore.

And then I scored 20.

Among the many difficult questions, there is a set of simple and easy questions that can bring joy and increase confidence...

It is believed that everyone has already easily answered this set of questions, but CSP-S may not be as easy. I hope everyone can have a great time in their first year of CSP-S and increase their reputation.

——Exam Setter

Me: ?

This is the first question, and the next two questions are too NaN.

Question#

Choosing courses in college is really a difficult thing!

Marco: "I want to graduate in two years! I want to take as many credits as possible! I will take all these courses!"

Elder: "You, Too Young! Look at the amount of homework, can you finish it?"

Marco (smile gradually disappearing.gif): "Then what should I do?"

Elder: "What else can you do? Drop the course!"

It is known that Marco has chosen N (1 ≤ N ≤ 500) courses, each course has credits wi, workload vi, and failure probability pi;

Among them, wi is a positive integer in the range [1,5], vi is a positive integer within the int range, and pi is a decimal number in the range [0,1];

Now Marco wants to drop some courses to minimize his workload, but if the total number of credits Marco gets does not reach the given MINX, he will be expelled.

Marco wants to know, in the case where the expected credits are greater than or equal to MINX, what is the minimum workload he can have.

Note: If Marco fails a course, he will have a workload of vi but will not receive the corresponding credits; otherwise, Marco will have a workload of vi and receive wi credits.

Input Format#

The first line contains a positive integer N, indicating the number of courses.

The next N lines contain three numbers separated by spaces, wi, vi, and pi, as described in the question.

The last line contains a positive integer MINX, indicating the minimum number of credits required.

Output Format#

One line containing a positive integer indicating the minimum workload.

Data Range#

There are 10 test cases in total, each worth 10 points.

For 10% of the data, 1 ≤ N ≤ 10.

For 30% of the data, 1 ≤ N ≤ 20.

For an additional 20% of the data, pi = 0.

For 100% of the data,

1 ≤ N ≤ 500,

wi is a positive integer and 1 ≤ wi ≤ 5,

pi can have up to 2 decimal places and 0 ≤ pi ≤ 1,

vi is a positive integer within the int range.

It is guaranteed that Marco will not be expelled if he chooses all the courses.

The extra spaces at the end of each line in the output will not affect the correctness of the answer.

Sample Input#

Sample Output#

Sample Explanation#

Only choose the second course, the expected credits are 2 * 0.5 = 1, and the workload is 1.

Approach#

At first, I thought of using f[i][j] to represent the maximum score obtained when considering the first i courses and having a workload of j.

Then I realized that the range of j is too large...

Then I thought of using f[i][j] to represent the minimum workload when considering the first i courses and having an expected score of j.

But the expected score is a decimal number!!

Then I randomly wrote a dfs for n<20 and a random dp for n>20.

This solution failed.

After the contest, I looked at the editorial:

Okay, got it!

There is also a precision issue.

Borrowing a figure from the solution:

What??

Then I found out that 100 - p * 100 doesn't work either.

But adding 0.01 or round(100 - p * 100) works??

Oh well, forget it. I'll remember to use round in the future.

Code#

Just a few lines...

#include <cstdio>
#include <algorithm>
#include <cmath>

const int MAXN = 505;

int w[MAXN], v[MAXN];
long long f[MAXN * MAXN];
int n;
int minx;
int maxW = 0;
long long ans = (1ll<<60ll);

int main (void) {
	freopen("young.in", "r", stdin);
	freopen("young.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		double p;
		scanf("%d%d", w + i, v + i);
		scanf("%lf", &p);
		w[i] *= round(100 - p * 100);
		maxW += w[i];
	}
	scanf("%d", &minx);
	minx *= 100;
	for (int i = 1; i <= maxW; ++i) {
		f[i] = (1ll<<60ll);
	}
	int sum = 0;
	for (int i = 1; i <= n; ++i) {
		sum += w[i];
		for (int j = sum; j >= w[i]; --j) {
			f[j] = std::min(f[j], f[j - w[i]] + v[i]);
		}
	}
	for (int i = minx; i <= sum; ++i) {
		ans = std::min(ans, f[i]);
	}
	printf("%lld\n", ans);
	return 0;
}