City Game

hdu1505:http://acm.hdu.edu.cn/showproblem.php?pid=1505

题解:给你一个字符矩阵,里面有R和F两种字符,然后让你找一个最大的子矩阵,这个最大的子矩阵只含有F。

题解:在队友的提示下和上一题的影响,我先处理出每一行,以该行为起点的连续F的高度,然后每一行的情况问题就转化成上一题的问题,然后枚举每一行就可以了。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int n,m;
char mp[N][N];
int dp[N][N];
int ll[N],rr[N],ans;
int main(){
int cas;
scanf("%d",&cas);
while(cas--){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
cin>>mp[i][j];
for(int i=;i<=m;i++){
int temp=;
for(int j=;j<=n;j++){
if(mp[j][i]=='F')
++temp;
else
temp=;
dp[j][i]=temp;
}
}
ans=;
for(int i=n;i>=;i--){
memset(ll,,sizeof(ll));
memset(rr,,sizeof(rr));
dp[i][]=-;dp[i][m+]=-;
for(int j=;j<=m;j++){
ll[j]=j;
if(j==)continue;
int t=j-;
while(dp[i][j]<=dp[i][t]){
ll[j]=ll[t];
t=ll[t]-;
}
}
for(int j=m;j>=;j--){
rr[j]=j;
if(j==m)continue;
int t=j+;
while(dp[i][j]<=dp[i][t]){
rr[j]=rr[t];
t=rr[t]+;
}
}
for(int k=;k<=m;k++){
ans=max(ans,(rr[k]-ll[k]+)*dp[i][k]);
}
}
printf("%d\n",ans*);
} }
上一篇:【2021年度总结】摸索探索


下一篇:寒假笔记本7:华师一2019高中招生考试化学部分简析