P6005 [USACO20JAN] Time is Mooney G

Description

有 $N$ 个城市，之间通过 $M$ 条单向道路来连接，每次到达城市 $i$ 可以获得 $m_i$。每次移动消耗一天，且移动 $T$ 天需要花费 $C\times T^2$。

从城市 $1$ 出发，最后回到城市 $1$，要求求出可以获得的最大值。

考虑dp做法。我们设 $f_{i,j}$ 表示在出差的第 $i$ 天，当前所在城市编号是 $j$ 时的最大贡献。那么最后的答案就是所有的 $f_{i,1}$ 的最大值。

考虑状态转移，显然，对于当前城市 $j$，可以从符合存在 $k\rightarrow j$ 的城市 $k$ 转移。所以建图的时候可以建反向边来帮助转移。

那么转移方程就是：

$$f_{i,j}=\max(f_{i-1,k}+m_j,f_{i,j})$$

其中 $k$ 满足存在 $k\rightarrow j$ 的边。

初始化时，$f_0,1=0$。所有的节点都要初始化为 $-1$，表示在第 $i$ 天时不可能在城市 $j$。
$i$ 的最大值可以直接设为 $1000$，因为在最极限的情况下，$i=1000$ 也会使得 $\max(m_i)\times i-i^2\times C\le 0$。

给定 $N$ 个礼物和 $N$ 头奶牛，对于每头奶牛而言，它会有一个愿望单排列 $w_i$，表示它希望收到的礼物编号。奶牛喜欢获得出现在愿望单中更早的礼物。

最初第 $i$ 号礼物对应第 $i$ 头奶牛，请重新分配礼物，使得每头奶牛都可以获得跟原来一样或者更好的礼物。

先考虑什么情况下奶牛可以获得更优的礼物。对于奶牛 $i$，假设其可以获得的更优的礼物编号是 $j$，那么奶牛 $j$ 由于没有了礼物需要换为一个更优的礼物 $k$。以此类推，只有当某一头奶牛的更优礼物是编号 $i$ 时，所有路径上的奶牛才能获得更优的礼物。

不难发现，此时会形成一个环。那么我们只需要使用Floyd判环即可。

Floyd 算法通过不断枚举中间点，来更新所有点对之间的最短路径。

具体过程类似DP，设 $f_{i,j}$ 表示从 $i$ 到 $j$ 的最短路径长度。那么转移方程就是：

$$f_{i,j}=\min(f_{i,j},f_{i,k}+f_{k,j})$$

其中 $k$ 是枚举的中间点。

同理，我们可以使用Floyd判环来判断是否存在环。我们可以把 $f_{i,j}$ 看作从 $i$ 到 $j$ 之间是否存在路径。那么转移方程就是：

$$f_{i,j}=f_{i,j}\lor(f_{i,k}\land f_{k,j})$$

其中 $k$ 是枚举的中间点。

如果在枚举完所有中间点后，$f_{i,i}$ 为 $1$，那么就说明存在环。

在一个二维方阵中，有 $n$ 个点，每个点有一个坐标 $(x_i,y_i)$。

可以选择一个矩形，请求出可以包围在这个矩形之中的不同的点子集的数量。空集也算作一种答案。

首先，题目的坐标范围都是 $10^9$，且根据题目，每行每列最多只会有一个点。那么我们可以通过离散化，把方阵缩小到一个 $n\times n$ 的方阵，每个点分别对应 $i,p_i$。

由于相同的点集算作一种答案，那么只需要枚举最小矩形即可。

那么我们可以枚举矩形的上下边界 $i,j$，设上下对应的左右边界 $l=\min(p_i,p_j),r=\max(p_i,p_j)$。

显然，对于 $i$ 和 $j$ 之间的所有点，如果横坐标在 $[l,r]$ 之间，那么这个点就会被包含在矩形之中，无法额外产生贡献。

所以只需要统计矩形左边和右边的点的数量，然后通过乘法定理来统计答案即可。

统计矩形左边和右边的点的数量可以在离散化之后，使用二维前缀和或者树状数组来统计。

注意空集也算一种答案，所以最终的答案数要加上 $1$。