错解:
#include<iostream>
using namespace std;
int m,n,mp[55][55],dp[202][100][100];
int maxx(int a,int b,int c,int d){
return max(max(a,b),max(c,d));
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>m>>n;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cin>>mp[i][j];
}
}
int ways=m+n;
for(int k=2;k<=ways;k++){
for(int i1=1;i1<=m;i1++){
for(int i2=1;i2<=m;i2++){
//if(i1<0||i1>m||i2<0||i2>m)continue;
int j1=k-i1,j2=k-i2;
int t=mp[i1][j1];
if(i1!=i2)t+=mp[i2][j2];
dp[k][i1][i2]=max(dp[k][i1][i2],maxx(dp[k-1][i1-1][i2],dp[k-1][i1][i2-1],dp[k-1][i1][i2],dp[k-1][i1-1][i2-1]))+t;
}
}
}
cout<<dp[ways][m][n];
}
==9/10次正解==
#include<iostream>
using namespace std;
// int N=66;
#define N 66
int mp[N][N];
int dp[N+N][N][N];
int m,n;
int main(){
cin>>m>>n;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++)cin>>mp[i][j];
}
for(int k=2;k<=m+n-1;k++){
for(int i1=1;i1<m;i1++){
for(int i2=i1+1;i2<=m;i2++){
int j1=k-i1,j2=k-i2;
int &x=dp[k][i1][i2];
int w=mp[i1][j1]+mp[i2][j2];
x=max(x,dp[k-1][i1][i2]+w);
x=max(x,dp[k-1][i1-1][i2]+w);
x=max(x,dp[k-1][i1][i2-1]+w);
x=max(x,dp[k-1][i1-1][i2-1]+w);
}
}
}
cout<<dp[m+n-1][m-1][m];
}
10/19正解:
#include<iostream>
using namespace std;
// int N=66;
#define N 66
int mp[N][N];
int dp[N+N][N][N];
int m,n;
int main(){
cin>>m>>n;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++)cin>>mp[i][j];
}
for(int k=2;k<=m+n-1;k++){
for(int i1=1;i1<m;i1++){
for(int i2=i1+1;i2<=m;i2++){
int j1=k-i1,j2=k-i2;
if(j1<=0||j1>n||j2<=0||j2>n)continue;
int &x=dp[k][i1][i2];
int w=mp[i1][j1]+mp[i2][j2];
x=max(x,dp[k-1][i1][i2]+w);
x=max(x,dp[k-1][i1-1][i2]+w);
x=max(x,dp[k-1][i1][i2-1]+w);
x=max(x,dp[k-1][i1-1][i2-1]+w);
}
}
}
cout<<dp[m+n-1][m-1][m];
}