我的博客

头条笔试题-数组两端轮流取数

目录
  1. 输入描述
  2. 输出描述
  3. 输入示例
  4. 备注
  • 解法
  • 题目描述

    今天你将接受智慧老人的试炼,智慧老人先将n个数(a_1 … a_n)从左到右排成一排,然后从你开始,你俩依次从这排数中取走排头或排尾的数,直到n个数被取完为止,双方的得分为去走的数的和。(假设智慧老人足够聪明。)
    请问你最多能得多少分呢?

    输入描述

    第一行有一个数字n,第二行有n个数字 a_1 .. a_n。

    输出描述

    一个数字:你的最大得分

    输入示例

    输入

    3
    1 1 1

    输出

    2

    备注

    数据范围

    1 <= a_i <= 10000 for all i

    对于n:

    其中30%的数据:1<=n<=10

    其中30%的数据:1<=n<=100(原题如此,可能是笔误)

    其中40%的数据:1<=n<=2000

    这里有类似的题目:
    https://nanti.jisuanke.com/t/48

    这里有一个解法,但是写有问题,数组会越界。

    解法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    import java.util.Scanner;

    public class Main {

    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int [][]sum = new int[n][n];
    int [][]dp = new int[n][n];
    int []a = new int[n];
    for (int i = 0; i < n; i++) {
    a[i] = sc.nextInt();
    dp[i][i] = a[i];
    sum[i][i] = a[i];
    }
    for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
    sum[i][j]=sum[i][j-1]+a[j];
    }
    }
    for(int i=n-2;i>=0;i--){
    for(int j=i+1;j<n;j++){
    dp[i][j]=sum[i][j]-Math.min(dp[i+1][j],dp[i][j-1]);
    dp[i][j]=sum[i][j]-Math.min(dp[i+1][j],dp[i][j-1]);
    }
    }
    System.out.println(dp[0][n-1]);
    }
    }

    计蒜客上那到题目只需把第 27 行改为

    1
    System.out.println(dp[0][n-1] + " " + (sum[0][n-1] - dp[0][n-1]));

    就可以了。

    评论无需登录,可以匿名,欢迎评论!