阿里笔试7.27 (第二题代码)(Java)

昨天去忘记笔试...只能回头看其他老哥分享的题自己做一下

第二题

有个藏宝架有n层,每层的宝物数量不一,每个宝物都有其价值,现在要求拿出m个宝物,并且需要遵守规则:

  1. 每次只能拿选定层的两端的宝物
  2. 要拿出的m个宝物的总价值是各种方案里最大的

    输入: n m
    下面每行代表每层,且第一个数是这层宝物的数量k,后面的则是k个宝物的价值
    4 1 2 4 5
    5 1 2 4 5 5
    样例:
    2 3
    2 3 2
    4 1 4 1 5
    输出:5+3+2=10

主要方法:DP

先用滑动窗口生成每一行取0-m个对应的最大值的一个矩阵 M:(m + 10) * n:

以样例为例:
0 3 5 5
0 5 6 10
之后做一个(m + 1)* n 的dp表:
类似背包的思想,从上往下,一层一层拿:
先只拿第一层:
0 3 5 5
(意义就是只拿第一层的时候,取的个数与对应最大总价值)
再加入第二层:
0 3 5 5
0 5 8 10

转移方程:dp[i] [j] = max( p[i-1] [j-k] + M[i] [k], dp[i-1] [j]) (0 <= k <= j)

时间复杂度:O(n^2*m)
空间复杂度:O(m*n)

代码

自测了一下,应该是好使,感兴趣的可以参考一下:

import java.util.*;
class test{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        List list = new LinkedList();
        while(in.hasNext()){
            int k = in.nextInt();
            int[] arr = new int[k];
            for (int i = 0; i < k; i++){
                arr[i] = in.nextInt();
            }
            list.add(arr);
        }
        LinkedList cur = new LinkedList();
        helper(list, m, cur);
        int res = helper(cur, m, n);
        System.out.println(res);
    }

    private static int helper(List cur, int m, int n){
        int[][] dp = new int[n][m + 1];
        for (int i = 0; i < n; i++){
            for (int j = 0; j <= m; j++){
                if (i == 0 && j != 0) {
                    dp[i][j] = cur.get(0)[j-1];
                }else if (j == 0) {
                    dp[i][j] = 0;
                }else {
                    int curMax = dp[i-1][j];
                    for (int k = 0; k <= j; k++){
                        curMax = Math.max(curMax, dp[i-1][j-k] + cur.get(i)[k]);
                    }
                    dp[i][j] = curMax;
                }
            }
        }
        return dp[n-1][m];

    }

    private static void helper(List list, int m, List resList){
        for (int[] cur : list){
            resList.add(genRow(cur, m));
        }
    }

    private static int[] genRow(int[] arr, int m){
        int[] res = new int[m+1];
        res[0] = 0;
        for (int i = 1; i <= m; i++){
            res[i] = maxSum(arr, i);
        }
        return res;
    }

    private static int maxSum(int[] arr, int m){
        int sum = 0;
        for (int i : arr) sum += i;
        if (m > arr.length) return sum;
        int res = Integer.MAX_VALUE; 
        for (int i = 0; i <= m; i++){
            int cur = 0;
            for (int j = 0; j < arr.length - m; j++){
                cur += arr[i+j];
            }
            res = Math.min(res, cur);
        }
        return sum - res;
    }
}
#阿里笔试##笔试题目##阿里巴巴##Java工程师#
全部评论
m的范围是10000哦,你时间效率没算错的话肯定过不了吧
点赞 回复
分享
发布于 2020-07-28 18:46

相关推荐

7 17 评论
分享
牛客网
牛客企业服务