关于为什么不能像战略游戏(P2016)一样用两个状态(dp[M][2])
查看原帖
关于为什么不能像战略游戏(P2016)一样用两个状态(dp[M][2])
151712
一架飞机楼主2021/3/17 17:35

因为战略游戏是守边,此题是守点。

如:1-2-3-4中选1、4。此题可以,前者不行。

战略游戏转移方程:

dp[x][0]+=dp[y][1];
dp[x][1]+=min(dp[y][0],dp[y][1]);

此题x可以由fa[x]控制,dp[x][0]可能由dp[y][0]转移过来。

所以要分 x可以由fa[x]控制 的情况。

2021/3/17 17:35
加载中...