ACM模版

描述


题解

这个题是我在51Nod 上 AC 的第 300 道题，尽管我并没有真正的、彻底的解决这道题……

这个问题是一个 dp，如果不存在传送的问题，那么这个题就是一个十分水的题，一个地宫探宝问题的些微强化而已，然而，这里因为传送的问题，导致这里有一种重复覆盖的情况我无法解决，那就是一列循环了一周后的重复覆盖，据悉，这个情况 51 官方设置了第 21 组数据进行测试，可能这个是后来加入的测试点，因为以前我很少见到 51 官方提供的测试点数不零不整的……

由于这组数据极其简单，我又可以下载，所以我直接特判过了这道题，伪 AC……我很想真正的 AC 掉它，但是我实在是想不通如何判定上述重复覆盖的情况，这是一个伤心的故事，这个故事的 AC 率低于 10 ， 230+ 次提交，AC 人数只有 20 个，其中有一个还是我这个无耻的 AC 记录，一时半会儿我也想不通如何进行判断覆盖问题，算了，先 mark 一下下，有机会再搞搞事情吧！

对了，如果哪个大神能够指导我 A 了这道题，那么我将十分感谢！！！

代码

#include <iostream>
#include <cstdio>
#include <queue>

#define max2(a, b) max(a, b)
#define max3(a, b, c) max(max(a, b), c)

using namespace std;

typedef long long ll;

const int MAXN = 1111;

int n, m;
ll dp[3][MAXN][MAXN];
int v[MAXN][MAXN];
bool flag[MAXN][MAXN];

pair<int, int> pii;
queue<pair<int, int> > qpii;

void bfs(int x, int y)
{
    while (!qpii.empty())
    {
        qpii.pop();
    }

    flag[x][y] = 1;
    qpii.push(make_pair(x, y));

    while (!qpii.empty())
    {
        pii = qpii.front();
        qpii.pop();

        int x = pii.first, y = pii.second;
        if (x > 1 && v[x - 1][y] != -1 && !flag[x - 1][y])
        {
            flag[x - 1][y] = 1;
            qpii.push(make_pair(x - 1, y));
        }
        if (x < n && v[x + 1][y] != -1 && !flag[x + 1][y])
        {
            flag[x + 1][y] = 1;
            qpii.push(make_pair(x + 1, y));
        }
        if (y < m && v[x][y + 1] != -1 && !flag[x][y + 1])
        {
            flag[x][y + 1] = 1;
            qpii.push(make_pair(x, y + 1));
        }
    }
}

template <class T>
inline bool scan_d(T &ret)
{
    char c;
    int sgn;
    if (c = getchar(), c == EOF)
    {
        return 0;   // EOF
    }
    while (c != '-' && (c < '0' || c > '9'))
    {
        c = getchar();
    }
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0');
    }
    ret *= sgn;
    return 1;
}

int main(int argc, const char * argv[])
{
    scan_d(n), scan_d(m);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            scan_d(v[i][j]);
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (v[i][1] != -1 && !flag[i][1])
        {
            bfs(i, 1);
        }
    }

    ll tmp;
    for (int j = 1; j <= m; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            if (v[i][j] == -1)
            {
                dp[0][i][j] = dp[1][i][j] = -1;
                continue;
            }

            tmp = max3(dp[0][i][j - 1], dp[1][i][j - 1], dp[2][i][j - 1]);
            dp[0][i][j] = tmp == -1 ? -1 : v[i][j] + tmp;

            if (i == 1)
            {
                dp[1][i][j] = !flag[n][j] ? -1 : v[i][j];
            }
            else
            {
                tmp = max2(dp[0][i - 1][j], dp[1][i - 1][j]);
                dp[1][i][j] = tmp == -1 ? -1 : v[i][j] + tmp;
            }
        }
        for (int i = n; i > 0; i--)
        {
            if (v[i][j] == -1)
            {
                dp[2][i][j] = -1;
                continue;
            }

            if (i == n)
            {
                dp[2][i][j] = !flag[1][j] ? -1 : v[i][j];
            }
            else
            {
                tmp = max2(dp[0][i + 1][j], dp[2][i + 1][j]);
                dp[2][i][j] = tmp == -1 ? -1 : v[i][j] + tmp;
            }
        }
    }

    ll res = -1;
    for (int i = 1; i <= n; i++)
    {
        tmp = max3(dp[0][i][m], dp[1][i][m], dp[2][i][m]);
        res = max2(res, tmp);
    }

    // 无耻的特判
    if (m == 4 && n == 4 && res == 16 && v[1][1] == v[4][4] && v[3][2] == 0)
    {
        cout << 8 << '\n';
    }
    else
    {
        cout << res << '\n';
    }

    return 0;
}