题目描述
blablabla
样例
blablabla
区间dp
blablabla
时间复杂度
参考文献
java 代码
package blueBridge.区间DP;
import java.util.Scanner;
public class acwing1388 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = 110;
int n = scanner.nextInt();
int[] g = new int[N];
int[][] f = new int[N][N];
int sum = 0;
for (int i = 1; i <= n; i++) {
g[i] = scanner.nextInt();
sum += g[i];
}
for (int len = 1; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
f[i][j] = Math.max(g[i] - f[i + 1][j], g[j] - f[i][j - 1]);
}
}
System.out.println((sum + f[1][n]) / 2 + " " + (sum - f[1][n]) / 2);
}
}