1 solutions
-
0
C++ :
#include<iostream> #define N 51 using namespace std; int max(int a,int b){return a>b?a:b;} int sum[N][N][N][N]={0}; int c[N][N]={0}; int main() { int n,m,i,j,h,k,a,b; cin>>m>>n; for(i=1;i<=m;i++) for(j=1;j<=n;j++) cin>>c[i][j]; for(i=1;i<=m;i++) for(j=1;j<=n;j++) for(h=1;h<=m;h++) for(k=1;k<=n;k++) { a=max(sum[i-1][j][h-1][k],sum[i][j-1][h][k-1]); b=max(sum[i-1][j][h][k-1],sum[i][j-1][h-1][k]); sum[i][j][h][k]=max(a,b)+c[i][j]; if(i!=h&&j!=k)sum[i][j][h][k]+=c[h][k]; } cout<<sum[m][n][m][n]; return 0; }Pascal :
var f:array[-50..101,-50..51,-50..51]of longint; a:array[-100..100,-100..100]of longint; n,i,j,k,m,maxn,s,minn,xxx:longint; function max(a,b:longint):longint; begin if a>b then max:=a else max:=b end; begin //assign(input,'message.in'); reset(input); //assign9output,'message.out'); rewrite(output); readln(n,m); for i:=1 to n do for j:=1 to m do read(a[i,j]); fillchar(f,sizeof(f),0); xxx:=m+n-2; for k:=2 to xxx do begin for i:=1 to n do for j:=i+1 to n do begin if abs(j-i) > 1 then begin f[k,i,j]:=max(f[k-1,i,j],f[k-1,i,j-1]); f[k,i,j]:=max(f[k,i,j],f[k-1,i-1,j]); f[k,i,j]:=max(f[k,i,j],f[k-1,i-1,j-1]); inc(f[k,i,j],a[i,k+1-i]+a[j,k+1-j]); end else begin f[k,i,j]:=max(f[k-1,i,j],f[k-1,i-1,j-1]); f[k,i,j]:=max(f[k,i,j],f[k-1,i-1,j]); inc(f[k,i,j],a[i,k+1-i]+a[j,k+1-j]); end; end; end; writeln(f[xxx,n-1,n]); // close(input); rewrite(output); end.Java :
import java.util.Scanner; public class Main { static int[][] map;// 好心程度 static int[][][][] dp; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); map = new int[52][52]; dp = new int[52][52][52][52]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { map[i][j] = sc.nextInt(); } } int sum = dp(m, n); System.out.println(sum); } static int dp(int m, int n) { for (int x1 = 1; x1 <= m; x1++) { for (int y1 = 1; y1 <= n; y1++) { for (int x2 = 1; x2 <= m; x2++) { for (int y2 = 1; y2 <= n; y2++) { /* * * 如果第一个人没有走到最后一行或最后一列,并且两个人没有重复 * 因为走到最后一行或最后一列,容易造成第二个人无路可走的情况 */ if ((x1 < m || y1 < n) && x1 == x2 && y1 == y2) { continue; } dp[x1][y1][x2][y2] = Math.max(Math.max( dp[x1 - 1][y1][x2 - 1][y2], dp[x1 - 1][y1][x2][y2 - 1]), Math.max( dp[x1][y1 - 1][x2 - 1][y2], dp[x1][y1 - 1][x2][y2 - 1])) + map[x1][y1] + map[x2][y2]; } } } } return dp[m][n][m][n]; } }
- 1
Information
- ID
- 19950
- Time
- 1000ms
- Memory
- 50MiB
- Difficulty
- (None)
- Tags
- # Submissions
- 0
- Accepted
- 0
- Uploaded By