1 solutions

  • 0
    @ 2025-11-5 20:01:33

    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