HDU 1505 City Game——递推

HDU 1505 City Game——递推

题意：给出一个用矩阵代表的城市图，R代表不可用，F代表可用，求面积最大的可用区域，这个区域必须是矩形

思路：建议先做一下HDU 1506

本题就是二维的HDU 1506，我们枚举每一行作为HDU 1506的底边，然后算出这个底边上每个元素向上能达到的最大高度(即和他上面第一个R之间的距离)，这就完全可以按照HDU1506 的方法求解，然后取所有情况的最大值即可

朴素的计算高度方法会超时（O（n^3））,我们可以递推计算高度，如果当前元素为R，那么高度为0，如果当前元素为F，那么高度为上一个高度+1。

ps:虽然我说的是从选择的底边向上计算高度，但是实际写起来我是从选择的底边向下计算高度，即把整个图倒过来，这样相对好写一些。

#include #include #include #include using namespace std;const int maxn = 1010;char c;int T, m, n, a[maxn][maxn], h[maxn][maxn], L[maxn], R[maxn];int main(){ scanf("%d", &T); while (T--) { scanf("%d %d", &m, &n); for (int i = 1; i <= n; i++) { a[0][i] = h[0][i] = 0; } for (int i = 1; i <= m; i++) { h[i][0] = -1, h[i][n + 1] = -1; for (int j = 1; j <= n; j++) { cin >> c; if (c == 'R') { a[i][j] = 1; h[i][j] = 0; } else { a[i][j] = 0; h[i][j] = h[i - 1][j] + 1; } } } int ans = 0; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { L[j] = j; int pos = j; while (h[i][j] <= h[i][pos - 1]) { L[j] = L[pos - 1]; pos = L[pos - 1]; } } for (int j = n; j >= 1; j--) { R[j] = j; int pos = j; while (h[i][j] <= h[i][pos + 1]) { R[j] = R[pos + 1]; pos = R[pos + 1]; } } for (int j = 1; j <= n; j++) { ans = max(ans, (R[j] - L[j] + 1) * h[i][j]); } } printf("%d\n", ans * 3); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。