std

std 2022-07-05 17:30:18 11 返回题目

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int m,n,ans;
int a[55][55],sum[55][55][55],f[55][55][55];
void solve() {
	for (int i=2; i<=n-1; i++) {
		for (int j=1; j<m; j++) {
			for (int k=j+1; k<=m; k++) {
				if (f[i][j][k]>-1) {
					for (int j2=j; j2<=k-1; j2++) {
						for (int k2=k; k2<=m; k2++) {
							f[i+1][j2][k2]=max(f[i+1][j2][k2],f[i][j][k]+sum[i][j][j2]+sum[i][k][k2]);
						}
					}
				}
			}
		}
	}
	for (int j2=1; j2<=m-1; j2++) {
		ans=max(ans,f[n][j2][m]+sum[n][j2][m]);
	}
	cout<<ans<<endl;
}

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 i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			sum[i][j][j]=a[j][i];
			for (int k=j+1; k<=m; k++) {
				sum[i][j][k]=sum[i][j][k-1]+a[k][i];
			}
		}
	}
	memset(f,255,sizeof(f));
	for(int k=2; k<=m; k++) {
		f[2][1][k]=sum[1][1][k];
	}
	solve();
	return 0;
}
{{ vote && vote.total.up }}