(more than 2022 cattle school four) A - Task Computing + dynamic programming (sort)

Title:

Sample input:

5 21 2 3 4 512000 11000 10000 9000 8000

Sample output:

8.5000000000000000

The meaning of the question: select m (a1,a2,...,am) from n tasks and sort them arbitrarily, the income is

Seek maximum profit.

Seeing the subscript distribution of the formula, we know that this value is related to the order of the tasks, so we should first consider what order to sort in. The common method is the gradual adjustment method, that is, Assume an order first, then exchange the positions of two adjacent elements, calculate the answers corresponding to the two sorting methods, and compare them to know what to sort by!

The following is the adjustment process:

We first sort the n tasks according to the above method, then m randomly selected from them all satisfy the above sorting rules, so the problem becomes how do we select m tasks from the n tasks.

What I thought at first was to use f[i][j] to represent the maximum value that can be obtained by selecting j tasks from the first i tasks, and then use a mul[i][j] to represent the value of f[i][j] state, then the recursion equation is:

f[i][j]=max(f[i-1][j],f[i-1][j-1]+w[i]*mul[i-1][j-1]), then update the mul array

But then I found out that this is a problem, because the maximum value we can get by selecting j tasks from the first i tasks is not necessarily the selection of j-1 tasks or j tasks from the first i-1 tasks.The maximum value obtained by the task, because the number of tasks selected from the first i-1 tasks will directly affect the product of the selected tasks, so this will have a great impact on the answer, so it cannot be done.

Positive solution:

The reason why the dynamic transition equation we just considered does not work is because The latter value depends on the previous two values, one is the product and the other is the sumformula, so we can't transfer backward directly according to the value of the sum formula, but after the deformation of the above formula, we can clearly find that we can deduce from the back to the front, so that the previous value is only followed byThe latter sum is related to the formula, not the product, so that we can perform dynamic transfer, but the update method will change slightly. This method is quite wonderful.

Let f[i][j] represent the maximum value of j tasks selected by considering the i~n tasks, then we directly update the array in reverse order

Dynamic transfer equation:f[i][j]=max(f[i+1][j],f[i+1][j-1]*p[i].q+p[i].w)

Here is the code:

#include#include#include#include#include