自动搬运

查看原文

来自洛谷，原作者为

	ybe2007 适度OI益脑，沉迷OI伤身

搬运于2025-08-24 22:38:48，当前版本为作者最后更新于2022-07-19 09:39:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

其实本质上是一道 $\text{dp}$ 题。

首先有如下事实：对于同代的同种小妖，我们只需考虑最早出生的那只。

原因：每只小妖的所有属性，包括成长时间，孵化种类及时间都是一定的。而我们要求的是最远到达的代数，所以只需考虑最早出生的那只即可。感性理解一下。

因此考虑动态规划。观察到 $t$ 的范围较大，所以不妨使用倍增优化。那么状态该如何设计呢？首先应当存下每一种的最小孵化时间，因为 $n\leq 100$，所以不妨把这个单独作为一个数组存下来。那么此时根据倍增，以代数为阶段进行转移更新最小值，倍增的答案累加到 $ans$ 中。

所以现在的目标就是如何较快地更新出每一种的最小值，为此我们可以预处理，令 $d_{p,i,j}$ 表示经过 $2^p$ 代，从 $i$ 出生到 $j$ 出生所需的最小时间，那么同样以倍增的形式进行转移，然后用类似 $\texttt{Floyd}$ 的方式更新最短路。注意，因为这里的阶段是单独作为一维的，所以不用按照 $\texttt{Floyd}$ 的方式在最外层枚举中转点的做法亦是可行的。然后更新答案的倍增倒序枚举，能更新就更新，根据二进制的相关知识，这样可以保证最优性。

时间复杂度 $O(n^3\times \log t)$。

#include<bits/stdc++.h>
#define N 105
using namespace std;
typedef long long ll;
int n,x[1005],y[1005];
ll T;
ll d[55][N][N];
ll now[N],mn[N];
int main()
{
	scanf("%d%lld",&n,&T);
	memset(d,0x3f,sizeof(d));
	for(int i=1;i<=n;i++)
	{
		int k,z;
		scanf("%d%d",&k,&z);
		for(int j=1;j<=k;j++) scanf("%d",&x[j]);
		for(int j=1;j<=k;j++) scanf("%d",&y[j]),d[0][i][x[j]]=min(d[0][i][x[j]],1ll*(z+y[j]));
	}
	for(int p=1;p<=50;p++)
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) d[p][i][j]=min(d[p][i][j],d[p-1][i][k]+d[p-1][k][j]);
	//d[p][i][j]表示从 i 到 j，繁殖(1<<p)代所需的最小年数 
	//不严格矩阵乘法，本质是倍增优化dp 
	ll ans=0;
	for(int p=50;p>=0;p--)
	{ 
		for(int i=1;i<=n;i++) mn[i]=1e18;
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mn[j]=min(mn[j],now[i]+d[p][i][j]);
		bool flag=0;
		for(int i=1;i<=n;i++) if(mn[i]<=T) flag=1;
		if(flag)
		{
			ans+=(1ll<<p);
			for(int i=1;i<=n;i++) now[i]=mn[i];
		}
	}
	printf("%lld\n",ans);
}