首页 > 编程学习 > Link with Level Editor I(图上DP,滚动数组)

题意

一个Level包含了若干个世界,每个世界包含\(m\)个点以及一些有向边,边的数量记为\(l_i\)(无重边和自环)。

玩家一开始站在第一个世界的\(1\)号点上。在每个世界,玩家要么静止在当前点上,要么沿着一条边,走到邻居节点。

然后,玩家将会被传送到下一个世界,并且保持传送前后点的编号不变。

在最后一个世界静止或者走完一步后,游戏终止(也就是在最后一个世界可以行动,但是不会被传送)。如果最终停在了\(m\)点上,那么玩家获胜。

现在要选取连续几个世界构成一个新的Level,使得玩家最后能够获胜。问最少需要选取多少个世界。

题目链接:https://ac.nowcoder.com/acm/contest/33187/L

数据范围

\(1 \leq n \leq 10^4\)
\(2 \leq m \leq 2 \times 10^3\)
\(0 \leq l \leq m(m-1)\)
\(0 \leq \sum\limits_{i=1}^n l_i \leq 10^6\)
空间限制:\(32M\)

思路

想了一晚上,终于把这道题搞懂了。。(感觉很多题解写得太简略,一些细节问题还得自己思考)

这道题是比较明显的分层图,但是由于空间限制,因此没法将图实际建出来。因此考虑DP。

\(f(i,j)\)表示到达第\(i\)个世界的第\(j\)个点,最少需要连续多少个世界(这里指的是传送到\(j\)点,而不是由同一世界中的邻居节点走到的)。这里实际情况是,如果我们将第\(i\)层作为最后一层的话,最终\(m\)点不一定是由\(i-1\)层转移过来的,有可能是由第\(i\)\(m\)的邻居转移过来的,这样\(f(i,j)\)的结果就不对了。

我们发现,最后一层不能进行传送等价于最后一层可以传送,传送到再下一层,因此计算结果为\(f(i + 1, m) - 1\)。第\(i+1\)层只用到了第\(i\)层的图,因此是合理的。

接下来考虑转移方程,如果\(j=1\),则\(f(i,j) = 1\)。如果\(j>1\),则\(f(i,j) = \min\limits_{k \in N_{i-1}(j)}(f(i-1, j), f(i-1,k))+1\)

由于空间限制,我们使用滚动数组。但是需要维护\(f(m)\)的最小值。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2010, inf = 0x3f3f3f3f;

int n, m;
int f[N], g[N];

int main()
{
    scanf("%d%d", &n, &m);
    memset(f, 0x3f, sizeof f);
    f[1] = 1;
    int ans = f[m];
    while(n --) {
        int l;
        scanf("%d", &l);        
        memcpy(g, f, sizeof f);
        for(int i = 2; i <= m; i ++) {
            if(g[i] != inf) {
                g[i] ++;
            }
        }
        while(l --) {
            int x, y;
            scanf("%d%d", &x, &y);
            if(y == 1) continue;
            g[y] = min(g[y], f[x] + 1);
        }
        ans = min(ans, g[m]);
        memcpy(f, g, sizeof g);
    }
    if(ans == inf) printf("-1\n");
    else printf("%d\n", max(1, ans - 1));
    return 0;
}
Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号