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

骑猪看日落 2023-09-24 15:28 43阅读 0赞

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

题目链接：[题目链接][Link 1]

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 题面： ###

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

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

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

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

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

![图片描述][9675cc37c3c655fc4a2729d4de21765a.png]

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

### 知识点 ###

*  最大子数组和
 *  动态规划

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 初始代码 ###

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)));
        }
    }

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 样例说明 ###

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

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

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 题解 ###

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

状态转移方程为 `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)));
        }
    }

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 总结 ###

要 AC 本题，必须学会**最大子数组和**和**动态规划**的算法，尽可能的获取卡片，以获取最高的积分，最终通过本题。

![在这里插入图片描述][3a01dc60e62c415b812015851343f1c0.png_pic_center]

[Designer]: https://blog.csdn.net/qq_41464123
[Link 1]: https://www.lanqiao.cn/contests/lqENT05/challenges/
[d20811fc24154b148e6372d8bd803dab.png_pic_center]: https://img-blog.csdnimg.cn/d20811fc24154b148e6372d8bd803dab.png#pic_center
[9675cc37c3c655fc4a2729d4de21765a.png]: https://img-blog.csdnimg.cn/img_convert/9675cc37c3c655fc4a2729d4de21765a.png
[3a01dc60e62c415b812015851343f1c0.png_pic_center]: https://img-blog.csdnimg.cn/3a01dc60e62c415b812015851343f1c0.png#pic_center