2022牛客多校第二场

L Link with Level Editor I

知识点：dp+滚动数组

题意：有n个世界，每个世界都有m个点和一些边（边可为0），从这些世界中选择一个子段进行游戏，规则从第一个世界的第一个节点出发，到达每个世界可以原地不动，也可以经过一条边，最终到达m点即为胜利。

要求选出一个尽可能短的子段，使得存在至少一种方案可以胜利。

思路：记录状态 dp[i][j]为若要在第i个世界到达j点，至少需要经历几个世界。答案为所有dp[i][m]的最小值，若一个都没有，则答案为-1。

转移方程：

​ 在第i个世界到达点j分两种情况：

​ 1、通过当前世界的边( b , j )到达j点，dp[i][j]=dp[i-1][b]+1;

​ 2、通过之前的世界到达j点，然后直接来到本世界即可，dp[i][j]=dp[i-1][j]+1;

​ 两者取最小值即可

结局了上述问题后还有一个问题就是，会内存超限，所以此处需要使用滚动数组来实现减少内存的操作，我们求解过程中只需要两个世界即可（当前世界和上一世界），所以一个深度为2的数组即可实现，可以假设当前世界为p（p取值只能为0 或 1），则上一世界一定为p^1，同理，下一世界也一定为p^1。

代码如下：

#include <iostream>
#include <vector>
#include <cstring>
#include <synchapi.h>
using namespace std;
int main() {
	int n,m;
	cin>>n>>m;
	int dp[2][2005];
	memset(dp,0x3f3f3f,sizeof(dp));//需初始化为INF
	int p=0;//初始世界为0；
	int ans=0x3f3f3f;//也需初始化为INF
	for(int i=1; i<=n; i++) {
		vector<int>ve[2005];
		int t;
		scanf("%d",&t);
		for(int j=1; j<=m; j++) {
			dp[p][j]=dp[p^1][j]+1;//当前世界的操作需要在继承上一世界的基础上进行。
		}
		for(int j=0; j<t; j++) {
			int b,e;
			scanf("%d%d",&b,&e);
			if(b==1) {
				dp[p][e]=1;//若此边是从点1到达的，则可直接从此世界开始，使得世界数目最少
			} else {
				dp[p][e]=min(dp[p][e],dp[p^1][b]+1); 
					/*此处不可用dp[p^1][b]+1替换,因为在此世界中可能有多个点指向e,导致dp[p][e]已经改变多次*/
			}
		}
		ans=min(ans,dp[p][m]);//求解答案
		p^=1;
	}
	if(ans==0x3f3f3f)cout<<-1;
	else cout<<ans;
}