1. Problem Description:

Niuniu is playing a CF game. The game time is T minutes. There are N questions. You can submit the code at any time during the game time. The score of question I is maxPoints[i]. The score of question I decreases by pointsPerMinute[i] per minute with the progress of the game. This is a CF game of dark. The score may be reduced to a negative number. It is known that question I needs to take time [i] to solve, How many points can I get at most?

Enter Description:
On the first line, enter two integers N,T (1 ≤ N ≤ 50, 1 ≤ T ≤ 100000)
On the second line, enter n integers maxPoints[i]
On the third line, enter n integers pointsPerMinute[i]
On the fourth line, enter n integers requiredTime[i]
1 ≤ maxPoints[i],pointsPerMinute[i],requiredTime[i] ≤ 100000

Output Description:
Output an integer
Example 1
input
1 74
502
2
47
output
408
Example 2
input
2 40000
100000 100000
1 100000
50000 30000
output
0
Example 3
input
3 75
250 500 1000
2 4 8
25 25 25
output
1200
Example 4
input
3 30
100 100 100000
1 1 100
15 15 30
output
97000
remarks:
Subtask 1: n < = 10
Subtask 2: n < = 20
Subtask 3: Unlimited

Link: https://ac.nowcoder.com/acm/problem/21314
Source: niuke.com

2. Train of thought analysis:

① By analyzing the topic, we can know that the essence of this topic is 01 knapsack model, which is only slightly different from 01 knapsack in the description of the problem, but it is easy to understand if it is transformed into 01 knapsack problem. The competition time is T minutes, which is equivalent to the maximum capacity of the backpack. N questions are equivalent to n items. The score of each question is equivalent to the value of the items. There are many restrictions on this question, that is, with the progress of the competition, each question will subtract a certain score, For this limitation of the problem, we can first solve the problems that consume more scores in a relatively short time. Specifically, we can solve the problems that consume more scores in a unit time first. For this condition, we can input maxPoints, pointsPerMinute on the console, requiredTime as a whole is sorted from the largest to the smallest according to the scores consumed per unit time. Next, you can use a one-dimensional list or array (python is the list and c/c++/java is the array) to solve the 01 knapsack problem. On the premise that the capacity of the backpack can take the current items, try to put the current items into the backpack to see if the value is greater. Because there is a condition that a certain score will be deducted from each topic as the competition progresses, we need to subtract the current time multiplied by the score of this topic per minute when calculating the current dp[i]. In fact, it is the sort (restriction) + 01 knapsack model.

② At the beginning, the python language was used, but the submission timed out. Later, the idea was changed to java, and the submission was passed. Python language can use tuples to add three maxPoints, pointsPerMinute and requiredTime as tuple elements to the list, so that the list can be sorted by lambda expression, and the sorting rules can be specified in the expression. java language can use object array to store three attribute values, and then you can also use lambda expression to specify the sorting rules to sort the object array. One problem to note is that the dp array needs to be declared as a long type so that overflow will not occur (the overflow occurs when it is declared as int at the beginning)

3. The code is as follows:

java code:

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
    public static class Node{
        long mPoints, pointsPerMinute, requiredTime;
        public long getmPoints() {
            return mPoints;
        }

        public long getPointsPerMinute() {
            return pointsPerMinute;
        }

        public long getRequiredTime() {
            return requiredTime;
        }

        public Node(long mPoints, long pointsPerMinute, long requiredTime){
            this.mPoints = mPoints;
            this.pointsPerMinute = pointsPerMinute;
            this.requiredTime = requiredTime;
        }

        @Override
        public String toString() {
            return mPoints + " " + pointsPerMinute + " " + requiredTime;
        }
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner((System.in));
        int n = sc.nextInt();
        int t = sc.nextInt();
        int[] maxPoints = new int[n];
        int[] pointsPerMinute = new int[n];
        int[] requiredTime = new int[n];
        for (int i = 0; i < n; ++i){
            maxPoints[i] = sc.nextInt();
        }
        for (int i = 0; i < n; ++i){
            pointsPerMinute[i] = sc.nextInt();
        }
        for (int i = 0; i < n; ++i){
            requiredTime[i] = sc.nextInt();
        }
        Node nodes[] = new Node[n];
        for (int i = 0; i < n; ++i){
            nodes[i] = new Node(maxPoints[i], pointsPerMinute[i], requiredTime[i]);
        }
        // Rules for sorting object arrays
        Comparator<Node> cmp = (o1, o2) -> {
            if ((float)o1.pointsPerMinute / o1.requiredTime > (float)o2.pointsPerMinute / o2.requiredTime){
                return -1;
            }else if ((float)o1.pointsPerMinute / o1.requiredTime < (float)o2.pointsPerMinute / o2.requiredTime){
                return 1;
            }
            return 0;
        };
        Arrays.sort(nodes, cmp);
        long dp[] = new long[t + 1];
        long res = 0;
        for (int i = 0; i < n; ++i){
            for (int j = t; j >= nodes[i].requiredTime; j--){
                dp[j] = Math.max(dp[j], dp[(int) (j - nodes[i].requiredTime)] + nodes[i].mPoints - j * (nodes[i].pointsPerMinute));
                res = Math.max(res, dp[j]);
            }
        }
        System.out.println(res + " ");
    }
}

python code:

if __name__ == '__main__':
    n, t = map(int, input().split())
    maxPoints, pointsPerMinute, requiredTime = list(map(int, input().split())), list(map(int, input().split())), list(map(int, input().split()))
    p = list(zip(maxPoints, pointsPerMinute, requiredTime))
    # User defined sorting rule: sort according to the consumption score in unit time from large to small
    p.sort(key=lambda x: (x[1] / x[2]), reverse=True)
    # print(p)
    # Next is the 01 knapsack problem
    dp = [0] * (t + 1)
    res = 0
    for i in range(n):
        j = t
        while j >= p[i][2]:
            dp[j] = max(dp[j], dp[j - p[i][2]] + p[i][0] - j * p[i][1])
            res = max(res, dp[j])
            j -= 1
    print(res)