自动搬运

查看原文

来自洛谷，原作者为

	Hanghang 2025冲冲冲

搬运于2025-08-24 22:59:03，当前版本为作者最后更新于2024-06-20 10:44:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P10544 [THUPC2024] 转化

来个暴力做法。

对每个物品的答案分别处理。设当前处理的物品为 $z$。

设 $f_{t,i}$ 表示经过了至多 $t$ 次转换，用一个 $i$ 最多能转化出 $f_{t,i}$ 个 $z$ 物品。

那么最终的答案为 $\sum f_{+\infty,i}\times a_i$，$a_i$ 为初始 $i$ 的物品个数，转移即枚举每种转移条件更新即可。

注意到这种松弛至多 $n$ 次，如果还能继续松弛那么说明物品可以无穷多。

复杂度为 $O(n^3m)$，实测非常快。

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

typedef __int128 ll;
const int N=103,M=1003;
ll n,m,sum,a[N],f[N],g[N],c[M],len[M],b[M][N];
void write(ll X)
{
	if(X<0){putchar('-');X=~(X-1);}
	int s[50],o=0;
	while(X){s[++o]=X%10;X/=10;}
	if(!o)s[++o]=0;while(o)putchar(s[o--]+'0');
	putchar('\n');
}
int main()
{
	int _n,_m;cin>>_n>>_m;n=_n;m=_m;
	for(int i=1,x;i<=n;i++)cin>>x,a[i]=x,sum+=n*a[i];
	for(int i=1;i<=m;i++)
	{
		int _c,_len;cin>>_c>>_len;c[i]=_c;len[i]=_len;
		for(int j=1,x;j<=len[i];j++)cin>>x,b[i][j]=x;
	}
	for(int t=1;t<=n;t++)
	{
		ll fl=0;
		for(int i=1;i<=n;i++)f[i]=i==t;
		for(int tim=1;tim<=n;tim++)
		{
			for(int i=1;i<=n;i++)g[i]=f[i];
			for(int i=1;i<=m;i++)
			{
				ll x=0;
				for(int j=1;j<=len[i];j++)x+=g[b[i][j]];
				f[c[i]]=max(f[c[i]],x);
			}
			ll cnt=0;
			for(int i=1;i<=n;i++)cnt+=f[i]==g[i];
			if(cnt==n)break;
			fl|=tim==n;ll s=0;
			for(int i=1;i<=n;i++)s+=f[i]*a[i];
		    if(s>(ll)1e33){fl=1;break;}
		}
		ll s=0;
		for(int i=1;i<=n;i++)s+=f[i]*a[i];
		if(fl)cout<<"infinity"<<endl;
		else write(s);
	}
}