题解 | #神性之陨#

神性之陨

https://ac.nowcoder.com/acm/contest/83521/H

题目: 神性之陨

考虑用二维 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;
}
全部评论

相关推荐

叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
机械打工仔:我来告诉你原因,是因为sobb有在线简历,有些HR为了快会直接先看在线简历,初步感觉不合适就不会找你要详细的了
投了多少份简历才上岸
点赞 评论 收藏
分享
码农索隆:这种hr,建议全中国推广
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务