给定:
+
和$Q$个减号 -
; ($P+Q=N-1$) ()
请你使用全部整数、加减号和括号,组成一个合法的算式($A_1~A_N$在算式中的顺序随意),使得算式的结果最大
注意加减号只能作为二元运算符出现在算式中,不能作为正负号
括号可以出现在算式最左和最右,例如 (((1+2)))
是合法的
例如对于样例数据, (2-1)+3
或 3+(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 - ((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); } }