牛客#2 L，多层图dp

最新推荐文章于 2025-06-02 20:51:47 发布

stdforces

最新推荐文章于 2025-06-02 20:51:47 发布

阅读量774

点赞数

文章标签：算法 c++ 数据结构

本文链接：https://blog.csdn.net/stdforces/article/details/126062534

版权

注意，内存限制32MB，存不下边

题意：

一个游戏内有 $n$ 个世界，每个世界有 $m$ 个节点和若干的有向边，玩家一开始在第一个世界的第一个节点，当我们在 $i$ 世界的 $j$ 点时，我们可以选择这个世界 $j$ 点的出发的一条边，到另外一个节点，但是在每个世界机会仅有一次，也可以不选择这样的边，在原地。假设我们在 $i$ 世界内最后到达的时 $j$ 点，那么我们会被传送至 $i + 1$ 世界的 $j$ 点（这样的传送仅会发生在 $i < n$ ），如果我们最后在 $n$ 世界并且停留在 $m$ 点，那我们就赢了。现在我们在这 $n$ 个世界内选择若干个连续的世界组成一个新的游戏，唯一的限制是要保证新游戏至少有一种赢的方法，要求找到符合条件的世界的最少数量。

方法：

我们设 $d p [i] [j]$ 为能到达 $i$ 世界的 $j$ 点的最后的出发世界，显然，转移只发生在相邻两个世界，因此我们可以滚动优化，用 $l a s t$ 保存上个世界， $d p$ 计算当前世界，问题再与怎么转移？如果我们知道当前世界有一条 $u\rightarrow v$ 的边，那么 $v$ 肯定是与 $u$ 有关系的，但能转移的是当前世界的 $u$ 还是上个世界的 $u$ 呢？假设在世界 $i$ 有这样的例子 $1\rightarrow 2 \rightarrow 3$ ，一开始知道边 $1\rightarrow 2$ ，显然 $d p [1] = i$ ，那么 $d p [2] = i$ ，再知道边 $2\rightarrow 3$ ，于是 $d p [3] = i$ ，这显然是不对的，因为每个世界仅有一次机会改变所在位置。因此我们选择从上个世界转移（这也是为什么不用一个数组来优化而用两个），那么知道边 $u\rightarrow v$ ，就可以给 $v$ 一个找更近的世界的机会，于是 $d p [v] = ma x (d p [v], l a s t [u])$ ，并且如果这个边是有关 $m$ 的，还改变了 $d p [m]$ 的值，我们就可以重新计算一遍 $an s$ ，也就是当 $d p [m]! = l a s t [m] ， an s = min (an s, i - d p [m] + 1)$ 。并且我们还需要考虑可以从现在这个世界出发的情况，所以我们特殊设 $l a s t [1] = i$ 。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int read()
{
	int ret=0,base=1;
	char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') base=-1;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		ret=(ret<<3)+(ret<<1)+ch-48;
		ch=getchar();
	}
	return ret*base;
}

const int inf=0x3fffffff;

int n,m,ans=inf,dp[2005],last[2005];

int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
	{
		last[1]=i;
		int t=read();
		while(t--)
		{
			int u=read(),v=read();
			dp[v]=max(dp[v],last[u]);
			if(v==m){
				if(dp[m]>last[m]) ans=min(ans,i-dp[m]+1);
			}
		}
		for(int j=1;j<=m;j++) last[j]=dp[j];
	}
	if(ans==inf) cout<<-1;
	else cout<<ans;
 	return 0;
}