70pts求助!!!!!(玄关)
查看原帖
70pts求助!!!!!(玄关)
846398
jomy楼主2024/4/18 22:21

从P1004改的,WA on #6,#8,#9

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=51;
int dp[N+N][N][N],s[N][N];
signed main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>s[i][j];
		}
	}
	for(int k=1;k<=n+m;k++){
		for(int i=1;i<=min(k,n);i++){
			for(int j=1;j<=min(k,m);j++){
				dp[k][i][j]=max({dp[k-1][i][j-1],dp[k-1][i][j],dp[k-1][i-1][j-1],dp[k-1][i-1][j]})+s[k-i+1][i]+s[k-j+1][j];
				if(i==j) dp[k][i][j]-=s[k-i+1][i];
			}
		}
	}
	cout<<dp[n+m][n][m];
	return 0;
}
2024/4/18 22:21
加载中...