AcWing 275. 传纸条
原题链接
中等
作者:
莫得感情的刷题机器
,
2020-08-18 18:40:18
,
所有人可见
,
阅读 435
和上一个题差不多 除了i1=i2的点不能走(赋0即可)
/**
* 有了前几个题的基础这个题就很简单了
* f(k,i1,i2)=重合?0:继续
* 继续:f(k,i1,i2)=max{f(k-1,i1-1,i2),f(k-1,i1,i2-1),f(k-1,i1-1,i2-1),f(k-1,i1,i2)}+两个元素值。
* 初始化f(2,1,1)=arr[1][1];
* k=3开始遍历
*
*/
import java.util.*;
public class Main{
public static void main(String [] args){
Scanner sc=new Scanner(System.in);
int m=sc.nextInt();
int n=sc.nextInt();
int[][] arr=new int[m+1][n+1];
int [][][] f=new int[m+n+1][m+1][m+1];
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
arr[i][j]=sc.nextInt();
for(int k=2;k<=n+m;k++){
for(int i1=1;i1<=m;i1++){
for(int i2=1;i2<=m;i2++){
int j1=k-i1,j2=k-i2;
if(j1<=0||j1>n||j2<=0||j2>n) continue;//保证坐标的合法性
if(i1==i2){
f[k][i1][i2]=0;//不能走同一点。
}else{
f[k][i1][i2]=Math.max(f[k-1][i1][i2],Math.max(f[k-1][i1-1][i2-1],Math.max(f[k-1][i1-1][i2],f[k-1][i1][i2-1])));
f[k][i1][i2]+=arr[i1][k-i1]+arr[i2][k-i2];
}
}
}
}
int res=Math.max(f[m+n-1][m][m-1],f[m+n-1][m-1][m]);//最后一步只能一个从左面一个从上面汇集到m,n点
System.out.println(res);
}
}