题目描述
blablabla
样例
import java.util.Scanner;
public class Main {
public static void maxSum(int[][] g, int N) {
int f[][][] = new int[2 * N + 1][N + 1][N + 1];
for (int k = 2; k <= 2 * N; k++) {
for (int i1 = 1; i1 < k && i1 <= N; i1++) {
if (k - i1 > N) continue;
for (int i2 = 1; i2 < k && i2 <= N; i2++) {
if (k - i2 > N) continue;
f[k][i1][i2] = Math.max(f[k][i1][i2], f[k - 1][i1 - 1][i2 - 1]);
f[k][i1][i2] = Math.max(f[k][i1][i2], f[k - 1][i1 - 1][i2]);
f[k][i1][i2] = Math.max(f[k][i1][i2], f[k - 1][i1][i2 - 1]);
f[k][i1][i2] = Math.max(f[k][i1][i2], f[k - 1][i1][i2] );
f[k][i1][i2] += g[i1][k - i1] + ((i1 == i2) ? 0 : g[i2][k - i2]);
}
}
}
System.out.println(f[2 * N][N][N]);
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while (scan.hasNext()) {
int N = scan.nextInt();
int g[][] = new int[N + 1][N + 1];
while (scan.hasNext()) {
int i = scan.nextInt();
int j = scan.nextInt();
int v = scan.nextInt();
if (i == 0 && j == 0 && v == 0) {
maxSum(g, N);
}
g[i][j] = v;
}
}
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla