暑期dp46道（9）——HDU 1505City Game 求最大子矩阵面积

暑期dp46道（9）——HDU 1505City Game 求最大子矩阵面积

题目链接：.php?pid=1505

可参考本人dp46道(8)的部分思路

这题是1506的变形，但是我个人觉得这个是比1505简单的，因为觉得思路更为清晰:

(一)读入数据并记录h[i][j]（这里用一个字符串s读入，对s[0]判断处理h[i][j]）;

(二)扫描枚举，求（i,j）的l[i][j]和r[i][j];

(三)（r[i][j]-l[i][j]-1）*h[i][j]枚举求最大值;

    for(int i=1;i<=n;i++){h[i][0]=h[i][m+1]=-1;for(int j=1;j<=m;j++){temp=j-1;while(h[i][temp]>=h[i][j])temp=l[i][temp];l[i][j]=temp;}for(int j=m;j>=1;j--)
	{temp=j+1;while(h[i][temp]>=h[i][j])temp=r[i][temp];r[i][j]=temp;}for(int j=1;j<=m;j++){ans=Max(ans,(r[i][j]-l[i][j]-1)*h[i][j]);}}

和1506题的差别就是这个行没有固定，但是理解起来反而更容易，对比1506还是先做这个更好，后面还有个变形....

附上代码：

#include<cstdio>
#include<cstring>
#include<string>
#define debug 0
#define M(a) memset(a,0,sizeof(a))
#define Max(a,b) ((a>b)?a:b)
const int maxn=1000+5;
int h[maxn][maxn],l[maxn][maxn],r[maxn][maxn];
int n,m,caseNum,ans;
void Do()
{int temp;for(int i=1;i<=n;i++){h[i][0]=h[i][m+1]=-1;//很重要，两边赋-1,方便求值 for(int j=1;j<=m;j++)//扫描枚举求l[i][j]和r[i][j] {temp=j-1;while(h[i][temp]>=h[i][j])temp=l[i][temp];l[i][j]=temp;}for(int j=m;j>=1;j--){temp=j+1;while(h[i][temp]>=h[i][j])temp=r[i][temp];r[i][j]=temp;}for(int j=1;j<=m;j++){ans=Max(ans,(r[i][j]-l[i][j]-1)*h[i][j]);//枚举求最大子矩阵面积 }}printf("%dn",3*ans);
}
int main()
{
#if debugfreopen(&#","r",stdin);
#endif//debugchar a[10];while(~scanf("%d",&caseNum)){while(caseNum--){ans=0;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)h[0][i]=0;//这个后来发现还是直接memset();初始化更省事些后面的题目用这个比较多 /*例如： #define M(a) memset(a,0,sizeof(a))M(h);*/for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%s",a);//字符串读入也可用：/*char a;while((a=getchar())==' '||a=='n');if(a=='R'){...}else{...}*/ if(a[0]=='R')h[i][j]=0;elseh[i][j]=h[i-1][j]+1;}Do();}}return 0;
}