CH1803:City Game 题解

思路

我在思考的时候能隐约的感觉到这应该是用单调栈做，但是始终无法得知做法的细节。理解之后，我来写下一些心得。

这道题的策略就是使用单调栈来排除无关答案。在读取每一行的时候，我们都可以计算出列的部分（因为我们是在读取每一行的时候计算，也就是说，我们在计算时读取并不是完成了的）能向上、向左和向右延伸的大小并且取最大值。

我把注释写在代码里了。看代码吧。

代码

// CH1803.cpp
// includings;
#include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;
const int maxn = 1010;
// n,m stands for the boundaries;
// h stands for the height of streching up;
// l stands for the left bound;
// r stands for the right bound;
int n, m, h[maxn], l[maxn], r[maxn], ans;
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            char ch;
            while (ch = getchar())
                if (ch == 'F' || ch == 'R')
                    break;
            // do statistics on the max height;
            if (ch == 'F')
                h[j]++;
            else
                h[j] = 0;
        }
        // rese;
        memset(l, 0, sizeof(l));
        memset(r, 0, sizeof(r));
        stack<int> st;
        for (int i = 1; i <= m; i++)
        {
            // delete the higher ones;
            while (!st.empty() && h[i] <= h[st.top()])
                st.pop();
            // set the bound;
            if (!st.empty())
                l[i] = st.top();
            else
                l[i] = 0;
            st.push(i);
        }
        // clear the stack;
        while (!st.empty())
            st.pop();
        for (int i = m; i >= 1; i--)
        {
            // delete the higher ones;
            while (!st.empty() && h[i] <= h[st.top()])
                st.pop();
            // set the right bound;
            if (!st.empty())
                r[i] = st.top();
            else
                r[i] = m + 1;
            st.push(i);
        }
        // do statistics on this;
        for (int i = 1; i <= m; i++)
            ans = max(ans, (h[i] * ((r[i] - 1) - (l[i] + 1) + 1)));
    }
    // output it;
    printf("%d\n", 3 * ans);
    return 0;
}