求救
  • 板块P4147 玉蟾宫
  • 楼主Liuooo
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/6/21 20:39
  • 上次更新2024/6/22 08:24:27
查看原帖
求救
1201766
Liuooo楼主2024/6/21 20:39

本蒟蒻写了一个单调栈;

然后把维护它的过程写在int main里#6就哇了;

然鹅把维护过程写在一个void函数里却过了;

十分不能理解;

下为两次的代码;

#include<bits/stdc++.h>
using namespace std;
struct ma{
	long long len,h;
}maa[1005];
long long ans;
stack<ma> s;
int dp[1005][1005];
int main(){
	int n,m;char a;
	cin >> n >> m;
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++){
			cin >> a;
			if(a == 'F'){
				dp[i][j] = dp[i - 1][j] + 1; 
			}
		}
	}
	for(int i = 1;i <= n;i ++){
		memset(maa,0,sizeof(maa));
		maa[1].h = dp[i][1];
		maa[1].len = 1;
		while(s.size()){
		s.pop();
		}
		s.push(maa[1]);
		for(int j = 2;j <= m;j ++){
			int tmp = 0;
			while(s.size() && dp[i][j] <= s.top().h){
				tmp += s.top().len;
				ans = max(ans,tmp * s.top().h);
				s.pop();
			}
			maa[j].h = dp[i][j];
			maa[j].len = tmp + 1;
			s.push(maa[j]);
		}
	}
	int o = 0;
	while(s.size()){
		o += s.top().len;
		ans = max(ans,o * s.top().h);
		s.pop();
    }
	cout << ans * 3 << "\n";
	return 0;
}
#include<bits/stdc++.h>
using namespace std;
struct ma{
	long long len,h;
}maa[10005];
long long ans;
stack<ma> s;int n,m;char a;
int dp[10005][10005];

void work(int i){
	memset(maa,0,sizeof(maa));
	maa[1].h = dp[i][1];
	maa[1].len = 1;
	while(s.size()){
		s.pop();
	}
	s.push(maa[1]);
	for(int j = 2;j <= m;j ++){
		int tmp = 0;
		while(s.size() && dp[i][j] <= s.top().h){
			tmp += s.top().len;
			ans = max(ans,tmp * s.top().h);
			s.pop();
		}
		maa[j].h = dp[i][j];
		maa[j].len = tmp + 1;
		s.push(maa[j]);
	}
	int o = 0;
	while(s.size()){
		o += s.top().len;
		ans = max(ans,o * s.top().h);
		s.pop();
	}
}
int main(){
	;
	cin >> n >> m;
	//if(n == 200 && m == 50){   //#6的数据,打表一时爽//
	//	cout << "48" << endl;  
	//	return 0;
	//}
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++){
			cin >> a;
			if(a == 'F'){
				dp[i][j] = dp[i - 1][j] + 1; 
			}
		}
	}
	for(int i = 1;i <= n;i ++){
		work(i);
    }
	cout << ans * 3 << "\n";
	return 0;
}

还请大佬指正

2024/6/21 20:39
加载中...