第一题：有n个关卡，每个关卡的道具都有一定的分值，同时还有可能有宝物掉落，可以选择捡或不捡宝物，如果捡宝物就不能捡道具，可以任意选择前往哪个关卡，求通关最大分

例：

5

1 0

3 0

7 1

2 1

1 1

预期结果：44

ac代码：

package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class test9 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        // 结果用int存放会越界，只能a63%，用long就好了
        long res = 0;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String[] str1 = br.readLine().split(" ");
            int x = Integer.parseInt(str1[0]), y = Integer.parseInt(str1[1]);
            if(y == 0) {
                res += x;
            } else {
                list.add(x);
            }
        }
        Collections.sort(list);
        for (int i = list.size() - 1; i >= 0 ; i--) {
            if(list.get(i) >= res) {
                res += list.get(i);
            } else {
                res *= 2;
            }
        }
        System.out.println(res);
    }
}

第二道：

求n*m矩阵当中正方形区域最大和，正方形区域都要为非负数

直接暴力

package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class test10 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int loop = Integer.parseInt(str[0]);
        for (int i = 0; i < loop; i++) {
            String[] str1 = br.readLine().split(" ");
            int n = Integer.parseInt(str1[0]), m = Integer.parseInt(str1[1]);
            int[][] index = new int[n][m];
            for (int j = 0; j < n; j++) {
                String[] str2 = br.readLine().split(" ");
                for (int k = 0; k < m; k++) {
                    index[j][k] = Integer.parseInt(str2[k]);
                }
            }
            System.out.println(dfs(index, n, m));
        }
    }

    public static int dfs(int[][] index, int n, int m) {
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int temp = method(index, i, j, n, m);
                res = Math.max(res, temp);
            }
        }
        return res;
    }

    public static int method(int[][] index, int i, int j, int n, int m) {
        int res = 0;
        int k = Math.min(n - i, m - j);
        boolean flag;
        for (int l = 0; l <= k; l++) {
            int temp = 0;
            flag = false;
            for (int a = i; a < i + l; a++) {
                for (int b = j; b < j + l; b++) {
                    if (index[a][b] < 0) {
                        flag = true;
                        break;
                    } else {
                        temp += index[a][b];
                    }
                }
                if (flag) {
                    break;
                }
            }
            if (flag) {
                continue;
            }
            res = Math.max(res, temp);
        }
        return res;
    }

}

#360#

9.9 360笔试

全站热榜

创作者周榜