华硕编程竞赛11月JAVA专场 G题飞行棋题解

Designer 小郑

发布于 2023-08-01 13:46:06

1810

发布于 2023-08-01 13:46:06

作者主页：Designer 小郑 作者简介：Java全栈软件工程师一枚，来自浙江宁波，负责开发管理公司OA项目，专注软件前后端开发（Vue、SpringBoot和微信小程序）、系统定制、远程技术指导。CSDN学院、蓝桥云课认证讲师，全栈领域优质创作者，在校期间参加PAT乙级考试获得满分，三年ACM竞赛经验，斩获国奖两项，省奖五项。热爱技术、专注业务、开放合作、乐于分享，期待你我共同成长！ 主打方向：Vue、SpringBoot、微信小程序

题目链接：题目链接

题面：

小王再次体验太空弹簧后，还是觉得飞机好玩，于是又来到了太空飞机场，想开着飞机遨游太空。

小张看到小王对太空飞机场如此感兴趣，于是命令手下将飞机场调整成了环形的一个有序圈，圈的周长为 N（1 < N < 5000)，也就是说一圈有 N 个飞机位，让小王玩得痛快。

这些临时排列的飞机场，每个飞机位都放有一张卡牌，卡牌上有个数 M（-5000 < N < 5000)，飞机飞到这个飞机位后，必须翻开这张卡牌，自己的积分加上这个数。

小王的飞机可以从九点钟开始，任意选一个飞机场作为启点，顺时针方向驾驶飞机，必须逐个停留每个飞机位，不得跨越，终点设为九点钟方向往南的第一个飞机位，飞机位编号如图所示。

游戏开始之前小王已经知道了每个飞机位的卡牌值，请问小王如何飞行才能让自己的积分最大化？

引用说明：以上图片来自于蓝桥云课。

知识点

最大子数组和
动态规划

初始代码

public class HMain {
    public static List<Integer> doWork(List<Integer> inputList) {
        List<Integer> ansObj = new ArrayList<>();
        // 最大积分值
        int max = -999;
        // 起始飞机位
        int k = 0;
        // 终止飞机位
        int l = 0;
        //代码编辑区 开始

        //代码编辑区 结束
        ansObj.add(max);
        ansObj.add(k);
        ansObj.add(l);
        return ansObj;
    }

    public static void main(String[] args) {
        //测试用例
        System.out.println((Objects.equals(Arrays.asList(8,3,6),doWork(Arrays.asList(1,-2,3,4,-5,6,-7))) ? "【√正确】" : "【X错误】 ") + "圈卡片值：1,-2,3,4,-5,6,-7，答案：" + doWork(Arrays.asList(1,-2,3,4,-5,6,-7)));
        System.out.println((Objects.equals(Arrays.asList(21,5,7),doWork(Arrays.asList(5,6,8,-99,7,7,7))) ? "【√正确】" : "【X错误】 ") + "圈卡片值：5,6,-1,5,4,-7，答案：" + doWork(Arrays.asList(5,6,8,-99,7,7,7)));
    }
}

样例说明

输入数据是一个整数数组 A，代表飞机场从九点钟方向开始，顺时针逐个飞机位的卡片值，数组长度不超过 5000，数组数据项的绝对值不超过 5000。

题目需要返回三个数 max（小王最高可获得的积分）、k（起始位置）、l（终止位置）。

题解

考察对动态规划的理解。九点钟方向顺时针一圈，可以理解为一条直线，卡片值也就是一个一维数组。

状态转移方程为 dp[i] = dp[i] + dp[i-1]，若 dp[i-1] 大于 0 则说明前面的积分可以延续采用。

若小于 0 则放弃前面的积分，从 0 积分重新开始，并更新起始位置。

参考代码如下：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;

public class HAns {
    private final static Integer[] ans = new Integer[6000];

    public static List<Integer> doWork(List<Integer> inputList) {
        List<Integer> ansObj = new ArrayList<>();
        // 最大积分值
        int max = -999;
        // 起始飞机位
        int k = 0;
        // 终止飞机位
        int l = 0;
        //代码编辑区 开始
        int n = inputList.size();
        List<Integer> numberList = new ArrayList<>();
        numberList.add(0);
        numberList.addAll(inputList);
        for(int i = 0; i < 6000; i ++) {
            ans[i] = 0;
        }
        for(int i = 1; i <= n; i ++) {
            ans[i] = Math.max(numberList.get(i), ans[i - 1] + numberList.get(i));
            if (ans[i] > max) {
                max = ans[i];
                l = i;
            }
        }
        int sum = 0;
        for (int i = l; i > 0; i--) {
            sum += numberList.get(i);
            if (sum == max) {
                k = i;
            }
        }
        //代码编辑区 结束
        ansObj.add(max);
        ansObj.add(k);
        ansObj.add(l);
        return ansObj;
    }

    public static void main(String[] args) {
        //测试用例
        System.out.println((Objects.equals(Arrays.asList(8,3,6),doWork(Arrays.asList(1,-2,3,4,-5,6,-7))) ? "【√正确】" : "【X错误】 ") + "圈卡片值：1,-2,3,4,-5,6,-7，答案：" + doWork(Arrays.asList(1,-2,3,4,-5,6,-7)));
        System.out.println((Objects.equals(Arrays.asList(21,5,7),doWork(Arrays.asList(5,6,8,-99,7,7,7))) ? "【√正确】" : "【X错误】 ") + "圈卡片值：5,6,8,-99,7,7,7，答案：" + doWork(Arrays.asList(5,6,8,-99,7,7,7)));
    }
}