40pts求助()
查看原帖
40pts求助()
502702
ABookCD楼主2023/3/4 08:47
#include<bits/stdc++.h>
using namespace std;
string s[410];
int su[410][410];
int dp[410][410];
int fs(int i,int x,int j,int y){
	return su[x][y]-su[i-1][y]-su[x][j-1]+su[i-1][j-1];
}

int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		s[i]=" "+s[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			su[i][j]=s[i][j]*2-97+su[i-1][j]+su[i][j-1]-su[i-1][j-1];
		//	cout<<i<<" "<<j<<" "<<su[i][j]<<endl; 
		}
	}
	memset(dp,~0x3f,sizeof dp);
	for(int i=1;i<=n;i++) dp[i][0]=0;
	for(int i=0;i<=m;i++) dp[0][i]=0;
	int ans=-1000000000;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int l=0;l<i;l++){
				dp[i][j]=max(dp[i][j],max(fs(l,i,1,j),dp[l][j]));
			}
			for(int l=0;l<j;l++){
				dp[i][j]=max(dp[i][j],max(fs(1,i,l,j),dp[i][l]));
			}
			ans=max(ans,dp[i][j]);
		}
	}
	cout<<ans<<endl;
	return 0;
} 
2023/3/4 08:47
加载中...