AcWing 275. 【Java】传纸条
原题链接
中等
作者:
tt2767
,
2020-01-10 23:23:32
,
所有人可见
,
阅读 809
// 开始没想到的是 1. 题目中的一次来一次回转化成两次去终点 2. 当搜索到点相等时另一个权值记0即可,代表这次路径不是最优的
// 这次y总开头讲了下通常状态的定义是怎么想的很有启发, 即先去掉描述程度的定语去考虑,不过本题的这个状态优化太难想到了
/* 基本做法(dp2)
1. 状态定义: 两条路线分别走到x1,y1 x2,y2 时的最大值 f[x1][y1][x2][y2]
2. 状态计算: 从最后一步来源切分,并加上当前的值,重合时只加一遍等价与降权为非最优节
路线1: 右,右,下,下
路线2: 右,下,下,右
3。 边界: 0
*/
/* 优化做法(dp1): 如果已经走了k步,可得: x1 + y1 == x2 + y2 == k + 2
1. 状态定义: 两条路线同时走,并且每条都已经走了k步,当前到达的横坐标是x1 x2 时的最大值 f[k][x1][x2]
2. 状态计算: 从最后一步来源切分,并加上当前的值,重合时只加一遍等价与降权为非最优节
路线1: 右,右,下,下
路线2: 右,下,下,右
3。 边界: 2 <= k <= m+n ; 1 <= x <= m && 1 <= k-x <= n;
*/
import java.util.*;
public class Main{
void run(){
int m = jin.nextInt();
int n = jin.nextInt();
for (int i = 1 ; i <= m ; i++){
for (int j = 1 ; j <= n ; j++){
cost[i][j] = jin.nextInt();
}
}
// int res = dp1(m, n);
int res = dp2(m, n);
System.out.println(res);
}
int dp2(int m, int n){
int[][][][] f = new int[maxN][maxN][maxN][maxN];
for (int x1 = 1 ; x1 <= m ; x1++){
for (int x2 = 1; x2 <= m ; x2++){
for (int y1 = 1 ; y1 <= n ; y1++){
for (int y2 = 1; y2 <= n ; y2 ++){
int t = 0;
int v = cost[x1][y1];
if (x1 != x2 && y1 != y2) v += cost[x2][y2];
t = Math.max(t, f[x1-1][y1][x2-1][y2] + v);
t = Math.max(t, f[x1][y1-1][x2-1][y2] + v);
t = Math.max(t, f[x1-1][y1][x2][y2-1] + v);
t = Math.max(t, f[x1][y1-1][x2][y2-1] + v);
f[x1][y1][x2][y2] = t;
}
}
}
}
return f[m][n][m][n];
}
int dp1(int m, int n){
int[][][] f = new int[maxN << 1][maxN][maxN];
for (int k = 2 ; k <= n+m ; k++){ // why k = 2?
int l = Math.max(1, k-n); // 1 <= x1 <= m, 1 <= k-x1 <= n
int r = Math.min(m, k-1);
for (int x1 = l ; x1 <= r ; x1++){
for (int x2 = l ; x2 <= r; x2 ++){
int t = 0;
int v = cost[x1][k-x1];
if (x1 != x2) v += cost[x2][k-x2];
t = Math.max(t, f[k-1][x1][x2] + v);
t = Math.max(t, f[k-1][x1][x2-1] + v);
t = Math.max(t, f[k-1][x1-1][x2] + v);
t = Math.max(t, f[k-1][x1-1][x2-1] + v);
f[k][x1][x2] = t;
}
}
}
return f[n+m][m][m];
}
int maxN = 52;
int[][] cost = new int[maxN][maxN];
Scanner jin = new Scanner(System.in);
public static void main(String[] args) {new Main().run();}
}