牛客多校2 - Link with Level Editor I（DP优化）

https://ac.nowcoder.com/acm/contest/33187/L

题意
给定 n 个世界，每个世界里有 m 个节点，$l_i$ 条边。
玩家初始在第一世界的 1 号节点。
在每个世界中，玩家要么选择待在当前节点不动，要么经过和该节点相连的一条边到达另一个节点（仅一次）。
然后，传送到下一个世界，玩家所在节点编号不变。
如果在最后一个世界，玩家所在 m 号节点，则胜利。

问，从这 n 个世界中，最少选出多少个连续的世界能够使得玩家胜利？

$1\le n\le 10^4,2\le m\le 2\times 10^3,0\le l_i\le m\times (m-1)$
$\sum l_i\le 10^6$

思路
当前世界只能由上个世界的节点到达，那么这个世界就用上个世界来转移。

定义 f[i, j] 表示，到达世界 i 的节点 j 最少使用的世界数。

两种转移方式：

1. 上个世界的一个节点不动，转移到当前世界，所用世界数 + 1：f[i, j] = min(f[i, j], f[i-1, j] + 1)；
2. 当前世界的节点 y 和当前世界的节点 x 连边（x 指向 y），节点 y 由当前世界的节点 x 转移，所用世界数为节点 x 的世界数：f[i, y] = min(f[i, y], f[i, x])；

这样转移看似没有问题，但是注意到题目中限制在每个世界中最多只能经过边一次，而第二种转移方式可能在更新过 f[i, y] 之后，y 节点再去更新别的节点，这样就会串着改，不能保证只经过边一次了！ 所以第二种转移方式不对。

如何保证只经过边一次呢？
可以直接从上一个世界的节点 x 下手，用上一个世界的 x 状态直接更新当前世界的 y。上个世界的 x 呆着不动转移过来花费 1，在这个世界有一条连边花费 0，所以整个花费就为 1：f[i, y] = f[i-1, x] + 1。

同时要注意：

• 因为初始在节点1，所以如果连边的一个起端点 x 为 1，那么转移到当前世界中没有花费。
• 因为要选出一段连续的，所以在任意节点都可以是最终世界，所以每个世界的答案要取 min。

所以整个状态转移方程为：

for(int j=1;j<=m;j++) f[0][j] = 1e9;
f[0][1] = 1;

int ans = 1e9;
for(int i=1;i<=n;i++)
{
	for(int j=1;j<=m;j++) f[i][j] = f[i-1][j] + 1; //呆着不动
	f[i][1] = 1;
	
	int k; cin >> k;
	while(k--)
	{
		int x, y; cin >> x >> y;
		if(x == 1) f[i][y] = 1; //注意和节点1相连的情况
		else f[i][y] = min(f[i][y], f[i-1][x] + 1); //依靠连边移动一次
	}
	
	ans = min(ans, f[i][m]);
}
if(ans >= 1e9) cout << -1;
else cout << ans;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

然后用滚动数组优化掉第一维即可：

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long
#define endl '\n'

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];
int f[2010], t[2010];

signed main(){
	Ios;
	cin >> n >> m;
	
	for(int i=2;i<=m;i++) f[i] = t[i] = 1e9;
	f[1] = t[1] = 1;
	
	int ans = 1e9;
	for(int i=1;i<=n;i++)
	{
		int k; cin >> k;
		
		for(int j=1;j<=m;j++) f[j] = min(f[j], t[j] + 1);
		
		while(k--){
			int x, y; cin >> x >> y;
			if(x == 1) f[y] = 1;
			else f[y] = min(f[y], t[x] + 1);
		}
		
		ans = min(ans, f[m]);
		for(int j=2;j<=m;j++) t[j] = f[j], f[j] = 1e9;
		t[1] = f[1] = 1;
	}
	if(ans != 1e9) cout << ans;
	else cout << -1;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41