订单问题

订单问题

Description

Rahul and Ankit are the only two waiters in Royal Restaurant. Today, the restaurant received N orders. The amount of tips may differ when handled by different waiters, if Rahul takes the ith order, he would be tipped Ai rupees and if Ankit takes this order, the tip would be Bi rupees.In order to maximize the total tip value they decided to distribute the order among themselves. One order will be handled by one person only. Also, due to time constraints Rahul cannot take more than X orders and Ankit cannot take more than Y orders. It is guaranteed that X + Y is greater than or equal to N, which means that all the orders can be handled by either Rahul or Ankit. Find out the maximum possible amount of total tip money after processing all the orders.

Rahul和Ankit是皇家餐厅仅有的两位服务员。今天，餐厅收到了N份订单。不同的服务员给的小费可能会不同，如果Rahul点了第i个菜，他会给Ai卢比，如果Ankit点了这个菜，小费是Bi卢比。为了使小费总额最大化，他们决定把订单分配给他们自己。一个订单只会由一个人处理。此外，由于时间限制，Rahul不能接受超过X个订单，Ankit不能接受超过Y个订单。可以保证X + Y大于或等于N，这意味着所有的订单都可以由Rahul或Ankit处理。在处理完所有的订单后，找出小费总额的最大值。

Input

• The first line contains one integer, number of test cases.
• The second line contains three integers N, X, Y.
• The third line contains N integers. The ith integer represents Ai.
• The fourth line contains N integers. The ith integer represents Bi.

•第一行包含一个整数，测试用例的数量。
•第二行包含三个整数N、X、Y。
•第三行包含N个整数。第i个整数代表Ai。
•第四行包含N个整数。第i个整数代表Bi。

Output

Print a single integer representing the maximum tip money they would receive.

打印一个整数，表示他们将收到的最大小费金额。

Sample Input

1
5 3 3
1 2 3 4 5
5 4 3 2 1

Sample Output

21

Solution

public class MaxTip {

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int caseNum = in.nextInt();
        for(int i = 0; i < caseNum; i++) {
            int orderNum = in.nextInt();
            int maxA = in.nextInt();
            int maxB = in.nextInt();
            int[] valueA = new int[orderNum];
            int[] valueB = new int[orderNum];
            for (int j = 0; j < orderNum; j++) {
                valueA[j] = in.nextInt();
            }
            for (int j = 0; j < orderNum; j++) {
                valueB[j] = in.nextInt();
            }
            System.out.println(getMaxTip(orderNum, maxA, maxB, valueA, valueB));
        }
    }

    public static int getMaxTip(int orderNum, int maxA, int maxB, int[] valueA, int[] valueB){
        int[][] value = new int[maxA + 1][maxB + 1];
        value[0][0] = 0;
        for(int i = 1; i <= maxA; i++){
            value[i][0] = value[i - 1][0] + valueA[i - 1];
        }
        for(int i = 1; i <= maxB; i++){
            value[0][i] = value[0][i - 1] + valueB[i - 1];
        }
        for(int i = 1; i <= maxA; i++){
            for(int j = 1; j <= maxB; j++){
                if(i + j <= orderNum){
                    value[i][j] = Math.max(value[i - 1][j] + valueA[i + j - 1], value[i][j - 1] + valueB[i + j - 1]);
                }
                else{
                    value[i][j] = Math.max(value[i - 1][j], value[i][j - 1]);
                }
            }
        }
        return value[maxA][maxB];
    }
}