Too Young - BuringStraw

Too Young#

I did a set of simulated questions today and scored over 20.

The person who set the questions for this set was violent throughout the process, ~~the joke was well told,——.~~

But I couldn't laugh anymore.

And then I scored over 20.

Among the many toxic 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. Happy bullying!

——Question setter

Me: ?

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

Question#

Choosing courses in college is really a distressing 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 credits of Marco cannot 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 his minimum workload.

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

Input Format#

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

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

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

Output Format#

One line containing a positive integer representing the minimum workload.

Data Range#

There are 10 test cases in this question, each worth 10 points.

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

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

For another 20% of the data, pi = 0

For 100% of the data,

1 ≤ N ≤ 500,

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

pi contains at most 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 do not affect the correctness of the answer.

Sample Input#

Sample Output#

Explanation#

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

Approach#

At first, I wanted to use f[i][j] to represent the maximum score obtained when considering the first i courses and the workload is j.

Then I found 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 the expected score is 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.

I got a score of zero for this question.

After the contest, I looked at the solution:

Okay, got it!

There is also a precision problem.

Borrowing the image from the solution:

What??

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

Adding 0.01 or round(100 - p * 100) works??

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;
}