HDU 1505 City Game

浅浅的花香味﹌ 2022-04-16 04:21 171阅读 0赞

## 原题目链接[HDU1505][] ##

--------------------

## 分类 ##

HDU 动态规划

--------------------

## 题意 ##

（dp）  
给你一个M\*N的区域。R代表被占用，F代表空闲。每块空闲  
的区域价值3美金，求全部由空闲区域围成的矩形的价值

## 样例输入输出 ##

Sample Input

2
    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
    
    5 5
    R R R R R
    R R R R R
    R R R R R
    R R R R R
    R R R R R

Sample Output

45
    0

--------------------

## 想法 ##

1506的升级版。不同的是，1505是二维的。把2维转换为以每一  
行为底，组成的最大面积就转换成了1506题。  
其中h\[i\]\[j\]表示第i行为底，第j列上方连续空闲位置的高度。  
遍历计算出该点向左右两边延伸的左右边界，从而计算出面积，最终比较  
计算出最大面积。乘以3就是最终的价值。

--------------------

## 代码 ##

436ms

#include<bits/stdc++.h>
    #define LL long long
    using namespace std;
    const int maxn = 1111;
    
    int mp[maxn][maxn],l[maxn],r[maxn];
    int n,m,t; 
    char ch;
    int main(){ 
    	cin >> t;
    	while(t--){ 
    		cin >> n >> m;
    		memset(mp,0,sizeof(mp));
    		memset(l,0,sizeof(l));
    		memset(r,0,sizeof(r));
    		for(int i=1;i<=n;i++){ 
    			for(int j=1;j<=m;j++){ 
    				cin >> ch;
    				if(ch == 'F'){ 
    					mp[i][j] = mp[i-1][j]+1;
    				}else{ 
    					mp[i][j] = 0;
    				}
    			}
    		}
    		
    		long long MAX = -1;
    		for(int i=1;i<=n;i++){ 
    			for(int j=1;j<=m;j++){ 
    				r[j] = l[j] = j;
    			}
    			l[0] = 1;
    			r[m+1] = m;
    			mp[i][0] = -1;
    			mp[i][m+1]= -1;
    			
    			for(int j=1;j<=m;j++){ 
    				while(mp[i][l[j]-1] >= mp[i][j])
    					l[j] = l[l[j]-1];
    			}
    			
    			for(int j=m;j>=1;j--){ 
    				while(mp[i][r[j]+1] >= mp[i][j])
    					r[j] = r[r[j]+1];
    			}
    			
    			for(int j=1;j<=m;j++){ 
    				long long temp = (r[j]-l[j]+1)*mp[i][j];
    				MAX = max(MAX,temp);
    			}
    		}
    		printf("%lld\n",MAX*3);
    	}
    }

[HDU1505]: http://acm.hdu.edu.cn/showproblem.php?pid=1505