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 }}