4 条题解

  • 3
    @ 2021-10-10 11:28:53
    #include <iostream>
    
    using namespace std;
    const int N = 60;
    int a[N][N];
    int dp[N][N][N][N];
    int main(){
    	int n, m;
    	cin >> n >> m;
    	for(int i = 1; i <= n; i++){
    		for(int j = 1; j <= m; j++){
    			cin >> a[i][j];
    		}
    	}
    	for(int i = 1; i <= n; i++){
    		for(int j = 1; j <= m; j++){
    			for(int x = 1; x <= n; x ++){
    				for(int y = 1; y <= m; y++){
    					int *t;
    					t = &dp[i][j][x][y];
    					*t = max(*t, dp[i-1][j][x][y-1]);
    					*t = max(*t, dp[i-1][j][x-1][y]);
    					*t = max(*t, dp[i][j-1][x-1][y]);
    					*t = max(*t, dp[i][j-1][x][y-1]);
    					*t += a[i][j] + a[x][y];
    					if(i == x && j == y)
    						*t -= a[x][y];
    				}
    			}
    		}
    	
    	}
    	cout << dp[n][m][n][m];
    } 
    
    • 0
      @ 2024-12-17 13:30:10
      #include <queue>
      #include <math.h>
      #include <stack>
      #include <stdio.h>
      #include <iostream>
      #include <vector>
      #include <iomanip>
      #include <string.h>
      #include <algorithm>
      using namespace std;
      #define int long long
      #define void inline void
      queue<int> Q;
      stack<int> S;
      vector<int> V;
      #ifndef SOMETHING_H
      #define SOMETHING_H
      #endif
      #define int long long
      inline int read(){
      	char c = getchar();
      	int s = 0;
      	while(c < '0' || c > '9')
      		c = getchar();
      	while(c >= '0' && c <= '9'){
      		s = s * 10 + c - '0';
      		c = getchar();
      	}
      	return s;
      }
      int n, m, ans[52][52][52][52], a[52][52];
      inline int f(int x1, int y1, int x2, int y2){
      	if(x1 == n && x2 == n && y1 == m && y2 == m)
      		return 0;
      	if(ans[x1][y1][x2][y2] != -1)
      		return ans[x1][y1][x2][y2];
      	int kkk = 0;
      	if(x1 < n && x2 < n)
      		if(a[x1 + 1][y1] != -1 && a[x2 + 1][y2] != -1)
      			kkk = max(kkk, f(x1 + 1, y1, x2 + 1, y2) + a[x1 + 1][y1] + a[x2 + 1][y2] - a[x1 + 1][y1] * (x1 == x2 && y1 == y2));
      	if(y1 < m && y2 < m)
      		if(a[x1][y1 + 1] != -1 && a[x2][y2 + 1] != -1)
      			kkk = max(kkk, f(x1, y1 + 1, x2, y2 + 1) + a[x1][y1 + 1] + a[x2][y2 + 1] - a[x1][y1 + 1] * (x1 == x2 && y1 == y2));
      	if(x1 < n && y2 < m)
      		if(a[x1 + 1][y1] != -1 && a[x2][y2 + 1] != -1)
      			kkk = max(kkk, f(x1 + 1, y1, x2, y2 + 1) + a[x1 + 1][y1] + a[x2][y2 + 1] - a[x1 + 1][y1] * (x1 + 1 == x2 && y1 == y2 + 1));
      	if(y1 < m && x2 < n)
      		if(a[x1][y1 + 1] != -1 && a[x2 + 1][y2] != -1)
      			kkk = max(kkk, f(x1, y1 + 1, x2 + 1, y2) + a[x1][y1 + 1] + a[x2 + 1][y2] - a[x1][y1 + 1] * (x1 == x2 + 1 && y1 + 1 == y2));
      	ans[x1][y1][x2][y2] = kkk;
      	return kkk;
      }
      void Main(){
      	n = read();
      	m = read();
      	memset(ans, -1, sizeof(ans));
      	for(int i = 1; i <= n; i++)
      		for(int o = 1; o <= m; o++)
      			a[i][o] = read();
      	cout << f(1, 1, 1, 1);
      	return;
      }
      signed main(int argc, char **argv){
      	Main();
      	return 0;
      }
      
      • 0
        @ 2023-12-10 20:47:50
        #include<bits/stdc++.h>
        using namespace std;
        const int N=55;
        int m,n,a[N][N],dp[N][N][N];
        int main(){
            cin>>m>>n;
            for(int i=1;i<=m;i++){
                for(int j=1;j<=n;j++){
                    cin>>a[i][j];
                }
            }
            for(int i=1;i<=m;i++)
                for(int j=1;j<=n;j++)
                    for(int k=1;k<=m;k++){
                        int l=i+j-k;
                        if(l>=1&&l<=n) {
                            int temp=max(max(dp[i-1][j][k-1],dp[i-1][j][k]),max(dp[i][j-1][k-1],dp[i][j-1][k]));
                            dp[i][j][k]=temp+a[i][j];
                            if(i!=k) dp[i][j][k]+=a[k][l];
                        }
                    }
            cout<<dp[m][n][m]<<endl;
            return 0;
        }
        
        • -4
          @ 2021-8-8 1:33:00

          C++ :

          #include<bits/stdc++.h>
          using namespace std;
          int a[51][51],n,m;
          unsigned int s[51][51][51][51];
          int main(int argc,char*argv[]){
              memset(a,0,sizeof(a));
              memset(s,0,sizeof(s));
              scanf("%d%d",&m,&n);
              for(int i=1;i<=m;i++){
              	for(int j=1;j<=n;j++){
              		 scanf("%d",&a[i][j]); 
          		}   
          		int a1,a2;
              	for(int j=1;j<=n;j++){
              		for(int k=1;k<=m;k++){
              			for(int l=1;l<=n;l++){
                      		a1=max(s[i][j-1][k][l-1],s[i-1][j][k][l-1]);
                      		a2=max(s[i-1][j][k-1][l],s[i][j-1][k-1][l]);
                      		s[i][j][k][l]=max(a1,a2)+a[i][j]+a[k][l];
                      		if(i==k&&j==l)s[i][j][k][l]-=a[i][j];
                  		}
          			}
          		}
          	}
              printf("%d",s[m][n][m][n]);
              return 0;
          }
          
          • 1

          信息

          ID
          186
          时间
          1000ms
          内存
          128MiB
          难度
          1
          标签
          递交数
          42
          已通过
          32
          上传者