60求助
查看原帖
60求助
553176
coding_hong楼主2022/2/4 16:43
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
const int maxn=55;
using namespace std;

int n,m,a[maxn][maxn],dp[2*maxn][maxn][maxn];
int main() {
	scanf("%d%d",&m,&n);
	for(int i=1; i<=m; i++)
		for(int j=1; j<=n; j++)
			scanf("%d",&a[i][j]);
	for(int k=2; k<=m+n; k++) {
		for(int i=max(1,k-m); i<=min(n,k-1)&&i<k; i++) {
			for(int j=max(1,k-m); j<=min(n,k-1)&&j<k; j++) {

				int t=a[i][k-i];
				if(i!=j)t=t+a[j][k-j];
				for(int aa=0; aa<=1; aa++) {
					for(int b=0; b<=1; b++) {
						dp[k][i][j]=max(dp[k][i][j],dp[k-1][i-aa][j-b]+t);
					}
				}
			}
		}
	}

	printf("%d\n", dp[n + m][n][n]);

	return 0;
}
2022/2/4 16:43
加载中...