首页 > 代码库 > HDU 1505 City Game

HDU 1505 City Game

2024-07-14 17:40:57   214人阅读

这题是上一题的升级版

关键在于条形图的构造，逐行处理输入的矩阵，遇到‘F‘则在上一次的条形图基础上再加1，遇到‘R‘则置为0

然后用上一题的算法，求每行对应条形图的最大矩阵的面积。

 

另外：本来是debug都不用就1A的节奏。可在输入数据上，一开始我用的是scanf读入字符 和 getchar跳过无效字符，在测试数据上是没有问题的，但一交上去就WA掉了。

看到别人的代码使用cin读入的。其实，如果输入数据不太大的话，cin还是比较放心好用的。

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7  8 const int maxn = 1010; 9 char map[maxn][maxn];10 int h[maxn], l[maxn], r[maxn];11 12 int main(void)13 {14     #ifdef LOCAL15         freopen("1505in.txt", "r", stdin);16     #endif17 18     int T;19     scanf("%d", &T);20     while(T--)21     {22         int row, col;23         scanf("%d%d", &row, &col);24         getchar();25         int i, j;26         for(i = 1; i <= row; ++i)27             for(j = 1; j <= col; ++j)28                 cin >> map[i][j];29 30         memset(h, 0, sizeof(h));31         l[1] = 1, r[col] = col;32         int t, ans = -1;33         for(i = 1; i <= row; ++i)34         {35             for(j = 1; j <= col; ++j)36                 if(map[i][j] == ‘F‘)37                     ++h[j];38                 else39                     h[j] = 0;40 41             for(j = 2; j <= col; ++j)42             {43                 t = j;44                 while(t > 1 && h[j] <= h[t-1])45                     t = l[t-1];46                 l[j] = t;47             }48             for(j = col-1; j > 0; --j)49             {50                 t = j;51                 while(t < col && h[j] <= h[t+1])52                     t = r[t+1];53                 r[j] = t;54             }55             for(j = 1; j <= col; ++j)56                 ans = max(ans, (r[j]-l[j]+1)*h[j]);57         }58         printf("%d\n", ans * 3);59     }60     return 0;61 }
代码君

 


联系
我们