MENU

算式最大值

March 18, 2019 • Read: 302 • 算法

给定:

  1. $N$个正整数$A_1,A_2, ... A_N$;
  2. $P$个加号+和$Q$个减号-; ($P+Q=N-1$)
  3. $K$对括号()

请你使用全部整数、加减号和括号,组成一个合法的算式($A_1~A_N$在算式中的顺序随意),使得算式的结果最大

注意加减号只能作为二元运算符出现在算式中,不能作为正负号

括号可以出现在算式最左和最右,例如(((1+2)))是合法的

例如对于样例数据,(2-1)+33+(2-1)等都是结果最大的算式

【输入】

第一行包含4个整数$N,P,Q$和$K$

第二行包含$N$个正整数$A_1$,A_2, ... A_N$

$2 ≤ N ≤ 100$
$P+Q+1=N$
$0 ≤ K ≤ 10$
$1 ≤ A_i ≤ 1000$

【输出】

最大算式结果

【样例输入】

3 1 1 1
1 2 3

【样例输出】

4

首先考虑没有括号的情况,如果没有括号,把$N$个数降序排列,将$p + 1$个最大的数加起来,减去剩下的$Q$个数

如果有括号,总能通过括号将$Q$个减号变为$Q-1$个加号,例如输入

5 0 4 2
5 4 3 2 1

通过括号可使得整个表达式变为

5 - ((1 - 2 - 3 - 4))

一般地,对于任意带有括号的表达式,总能转化为a - (b - c - d - ...)的形式,此时只需要b最小,就能使整个表达式的值最大

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int p = cin.nextInt(); // +
        int q = cin.nextInt(); // -
        int k = cin.nextInt(); // ()
        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++) 
            arr[i] = cin.nextInt();
        
        Arrays.sort(arr, Collections.reverseOrder()); // Order by desc
        int ans = 0;
        if (k == 0) {
            for (int i = 0; i <= p; i++) 
                ans += arr[i];
            for (int i = p - 1; i < n; i++)
                ans -= arr[i];
        } else {
            for (int i = 0; i < n - 1; i++)
                ans += arr[i];
            ans -= arr[n - 1];
        }
        System.out.println(ans);
    }
}
Archives Tip
QR Code for this page
Tipping QR Code