本文共 2400 字,大约阅读时间需要 8 分钟。
有一天,小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫,玉蟾宫宫主蓝兔盛情地款待了它们,并赐予它们一片土地。
这片土地被分成N*M个格子,每个格子里写着’R’或者’F’,R代表这块土地被赐予了rainbow,F代表这块土地被赐予了freda。
现在freda要在这里卖萌。。。它要找一块矩形土地,要求这片土地都标着’F’并且面积最大。
但是rainbow和freda的OI水平都弱爆了,找不出这块土地,而蓝兔也想看freda卖萌(她显然是不会编程的……),所以它们决定,如果你找到的土地面积为S,它们每人给你S两银子。
第一行两个整数N,M,表示矩形土地有N行M列。
接下来N行,每行M个用空格隔开的字符’F’或’R’,描述了矩形土地。
输出一个整数,表示你能得到多少银子,即(3*最大’F’矩形土地面积)的值。
5 6
R F F F F F F F F F F F R R R F F F F F F F F F F F F F F F
45
这道题可以用一种叫 悬线法 的方法!
所谓悬线法,for(int i=1;i<=n;i++){ int t=0; for(int j=1;j<=m;j++){ if(a[i][j])l[i][j]=t; else L[i][j]=0,t=j; //将L[i][j]赋值为0是因为待会dp的时候l要去max,所以就直接赋为0 } t=m+1; for(int j=m;j>=1;j--){ if(a[i][j]) r[i][j]=t; else R[i][j]=m+1,t=j; //同理R待会要取min所以就赋值成为m+1 } }
#includeusing namespace std;const int maxn = 1005;int n,m,ans;int a[maxn][maxn];int r[maxn][maxn],l[maxn][maxn],h[maxn][maxn],L[maxn][maxn],R[maxn][maxn];inline void DP(){ for(int i=1;i<=n;i++){ int t=0; for(int j=1;j<=m;j++){ if(a[i][j])l[i][j]=t; else L[i][j]=0,t=j; } t=m+1; for(int j=m;j>=1;j--){ if(a[i][j]) r[i][j]=t; else R[i][j]=m+1,t=j; } } for(int i=1;i<=m+1;i++) R[0][i]=m+1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]){ h[i][j]=h[i-1][j]+1; L[i][j]=max(l[i][j]+1,L[i-1][j]); R[i][j]=min(r[i][j]-1,R[i-1][j]); ans=max(ans,(R[i][j]-L[i][j]+1)*h[i][j]); }}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ char x;cin>>x; if(x=='F') a[i][j]=1; else a[i][j]=0; } DP(); printf("%d\n",3*ans); return 0;}
对比一下 可以发现,那个题不需要额外开数组的原因是,上下两个数不一样才会进行转移,如果上下两行都不同,那么它们就是大的矩阵。这样刚好可以覆盖所有情况。
而这一题,如果是1就会进行转移,假如不开额外数组的话就会GG。2 6
F F R R F F F F F F F F 这样的话,最大的显然是最后一行,但是此时的黄色部分已经被“污染”了, 而中间的那两个1的上一行是0,所以它们的值无法更新到正确答案。!转载地址:http://iyuci.baihongyu.com/