More than 2022 cattle school training topic Link with the second L Level Editor I

题目链接

Link with Level Editor I

题目大意

大概意思就是,给了我们$n$个世界,每个世界有$m$个点,There are several directed edges in each world,will connect some points.我们需要从1号点出发,最终走到$m$号点,Each time you can choose to choose a directed edge at the current point of the current world to go to another point,Or teleport directly to the next world,The question asks us the minimum need to choose how many worlds can be achieved from1走到$m$.

题解

考虑DP,设$f_{i,j}$表示在第$i$world to go$j$点,Which world to start from at the latest,Because of the problem card memory,We need to optimize it with rolling arrays.And also need to pay attention to some details of the state transition process,If the current directed edge is from1号点出发的,We need to write the current latest world$i$.具体看代码

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 2010, inf = 0x3f3f3f3f;
int f[2][maxn];
int n, m;
int main()
{
    
	cin >> n >> m;
	memset(f, -0x3f, sizeof f);
	int res = inf;
	for(int i = 1; i <= n; i ++){
    
		int num; cin >> num;
        f[(i - 1) & 1][1] = i;  // 尤其需要注意
		for(int j = 1; j <= m; j ++) f[i & 1][j] = f[(i - 1) & 1][j];
		while(num --) {
    
			int a, b; cin >> a >> b;
			f[i & 1][b] = max(f[i & 1][b], f[(i - 1) & 1][a]);
			if(b == m) res = min(res, i - f[i & 1][m] + 1);
		}
	}
	if(res >= inf / 2) cout << -1 << endl;
	else cout << res << endl;
}