AcWing 275. 传纸条
原题链接
中等
作者:
不知名的fE
,
2024-12-05 18:25:13
,
所有人可见
,
阅读 1
import java.util.*;
public class Main {
static final int N = 53;
static int[][] g = new int[N][N];
static int[][][] f = new int[2 * N][N][N];
static int n, m;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] s1 = sc.nextLine().split(" ");
n = Integer.parseInt(s1[0]); m = Integer.parseInt(s1[1]);
for (int i = 1; i <= n; i++) {
String[] s2 = sc.nextLine().split(" ");
g[i] = toIntArr(s2);
}
int ans = dp();
System.out.println(ans);
}
static int dp() {
for (int k = 2; k <= n + m; k ++ )
for (int i = Math.max(1, k - m); i <= n && i < k; i ++ )
for (int j = Math.max(1, k - m); j <= n && j < k; j ++ )
for (int a = 0; a <= 1; a ++ )
for (int b = 0; b <= 1; b ++ )
{
int t = g[i][k - i];
if (i != j || k == 2 || k == n + m)
{
t += g[j][k - j];
f[k][i][j] = Math.max(f[k][i][j], f[k - 1][i - a][j - b] + t);
}
}
return f[m + n][n][n];
}
static int[] toIntArr(String[] str) {
int[] res = new int[str.length + 1];
for (int i = 1; i <= str.length; i++) res[i] = Integer.parseInt(str[i - 1]);
return res;
}
}