题解 | #神性之陨#

题目: 神性之陨

考虑用二维 dp[i][j] 维护第 列第 行作为当前列连续选择方块的最下端时的合法性.

转移方法:

1. 当 a[i] != 1 时, 对于每一个 dp[i-1][j] = 1 都要转移向上下两个方向, 即 dp[i][j+a[i]-1] 和 dp[i][j](第 列第 行到第 行)

2. 当 a[i] == 1 时, 对于每一个 dp[i-1][j] == 1, dp[i][(j-a[i-1] + 1) ~ j] 都合法.

具体看代码:

int solve(int _) {
    int n, m;
    cin >> n >> m;
    vector<int>a(m + 1);
    for (int i = 1; i <= m; ++i) {
        cin >> a[i];
    }

    vector<vector<int>>dp(m + 1, vector<int>(n + 1, 0));//dp[i][j]能否为某列的最下点
    for (int i = 1; i <= n; ++i)dp[1][i] = 1;

    for (int i = 2; i <= m; ++i) {
        if (a[i] == 1) {
            int p = 1;
            for (int j = 1; j <= n; ++j) {
                if (!dp[i - 1][j])continue;
                int low = j - a[i - 1] + 1;
                int up = j;
                for (int y = max(p, low); y <= min(n, up); y++)
                    dp[i][y] = 1;
                p = max(p, up);
            }
        }
        else {
            for (int j = 1; j <= n; ++j) {
                if (!dp[i - 1][j])continue;
                int low = j + a[i] - 1;
                int up = j - a[i - 1] + 1;
                if (low <= n)dp[i][low] = 1;
                if (up - a[i] + 1 >= 1)dp[i][up] = 1;
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (dp[m][i])ans++;
    }
    return ans;
}