求助一道新手dp题
  • 板块灌水区
  • 楼主zty_luogu
  • 当前回复8
  • 已保存回复8
  • 发布时间2021/8/26 21:22
  • 上次更新2023/11/4 08:52:39
查看原帖
求助一道新手dp题
366595
zty_luogu楼主2021/8/26 21:22

是求最大子矩阵的

总是有点小问题

大数据都过了,小数据没过...

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define f(III,MMM,NNN) for(register int III=MMM;III<=NNN;III++)
typedef long long int ll;
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
int a[1010][1010]={},ans=-inf;
int s[1010][1010]={}; 
const int N=1010;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	int n,m;
	cin>>n;
	m=n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			s[i][j]=s[i-1][j]+a[i][j];
		}
	}
	for(int i=1;i<=n-1;i++){//枚举起始行 
		for(int j=i+1;j<=n;j++){//枚举终止行 
			int dp[1010]={};
			memset(dp,-127,sizeof(dp));
			for(int k=1;k<=m;k++){
				dp[k]=max(s[j][k]-s[i][k],s[j][k]-s[i][k]+dp[k-1]);
				ans=max(ans,dp[k]);
			}
		}
	}
	cout<<ans;
	return 0;
}

原题,感谢

2021/8/26 21:22
加载中...