首页 > 3.22阿里笔试第二题,测试能过,提交0%
头像
GoRight
编辑于 2021-04-15 14:26
+ 关注

3.22阿里笔试第二题,测试能过,提交0%

写的动态规划代码过了测试用例,但是提交的时候0%,请各位大佬帮忙看看问题出在哪
代码有一些冗余的地方,为了保持和提交时一致,并没有做更改,只是添加了注释
和这个ac的代码也比对过没发现什么问题,希望各位大佬能帮忙发现问题所在
各位大佬救救孩子吧,不想下次再遇到这种情况了
QAQQAQQAQ
代码如下
import java.util.Scanner;

public class Main {
    //动态规划,返回以[i,j]段玩游戏所得到的最大值(j是包括在内的)
    public static int max(int i,int j,int[] sum,int[][] dp){
        if(dp[i][j]!=-1){
            return dp[i][j];
        }
        //如果只有两个数,则返回其中较小的那个数
        else if((i+1)==j){
            dp[i][j] = Math.min(sum[i+1]-sum[i],sum[j+1]-sum[j]);
            return dp[i][j];
        }

        else{
            int res = 0;
            //遍历切分点(切分点为右边第一个数坐标)
            for(int pos=i+1;pos<=j;pos++){
                //分别求左边和右边的数字和
                int l = sum[pos]-sum[i],r=sum[j+1]-sum[pos];
                //如果右边数字和小,则获得右边的分数并用右边继续游戏
                if(l>r){
                    res = Math.max(res,r+max(pos,j,sum,dp));
                }
                //如果左边数字和小,则获得左边的分数并用左边继续游戏
                else if(l<r){
                    res = Math.max(res,l+max(i,pos-1,sum,dp));
                }
                //如果两边一样大,则分别玩游戏取最大值
                else{
                    res = Math.max(res,Math.max(l+max(i,pos-1,sum,dp),r+max(pos,j,sum,dp)));
                }
            }
            dp[i][j] = res;
            return res;
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int[] values = new int[n];
            for (int i = 0; i < n; i++) {
                values[i] = in.nextInt();
            }
            int[][] dp = new int[n+1][n+1];
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    dp[i][j]=-1;
                }
            }
            //只剩一个数字的时候游戏结束
            for(int i=0;i<n;i++){
                dp[i][i] = 0;
            }
            int[] sum = new int[n+1];
            //前缀和数组,[i,j]段的和为sum[j+1]-sum[i]
            for(int i=1;i<=n;i++){
                sum[i] = sum[i-1]+values[i-1];
            }

            int res =  max(0,n-1,sum,dp);
            System.out.println(res);
        }
    }
}

全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐