自动搬运

查看原文

来自洛谷，原作者为

	Crazyouth 系统维护，该内容暂不可见。:)

搬运于2025-08-24 22:25:48，当前版本为作者最后更新于2024-09-10 15:02:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言

这个题建议评蓝，细节处理太多了，找一句话提及的人花了我一天。

分析

注意到这题很像一个最长上升子序列弱化，因此想到 dp。令 $dp_i$ 表示以第 $i$ 句话结尾的最长对话长度，不难发现它可以从第 $i$ 句话所提及到不是自己的人里面转移。为了方便转移，我们令 $lst_s$ 表示名字为 $s$ 的人所发的话里面下标小于当前处理到的话的下标，且 $dp$ 值最大的一句，在每句话处理后再处理 $lst$。

接下来就是处理每句话提及到的人了。依题意得，每个被提及的人名前必须带空格，因此考虑以空格作为分隔符，把句子拆成单词，然后弃掉所有不以 @ 开头的单词。由于题目并没有说提及的人名字后带空格，因此对于每个以 @ 开头的单词，需要将它的每个含第一个字符的字串分别进行查找，然后进行转移。

最后选择最大的 dp 值输出答案，并找到它转移过来的方向，倒着输出即可。

有一个小点要注意：使用 getline 的话必须让程序读取一个空行再正式输入每一句话。

AC Code

#include <bits/stdc++.h>
using namespace std;
int dp[50010],from[50010],pos[50010],fans[50010];
map<string,int> lst;
string s[50010],str;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,cnt=0;
	cin>>n;
	getline(cin,s[0]);
	for(int i=1;i<=n;i++) getline(cin,s[i]),dp[i]=1;
	for(int i=1;i<=n;i++)
	{
		int flag=0;
		string res="",name;
		for(int j=0;j<s[i].size();j++)
		{
			if(!flag&&s[i][j]==':')
			{
				flag=1;
				name=res;
				res="";
				continue;
			}
			if(flag&&s[i][j]==' ')
			{
				res="";
				continue;
			}
			res+=s[i][j];
			if(flag&&res[0]=='@'&&res!=name)
			{
				if(lst[res])
				{
					if(dp[lst[res]]+1>dp[i])
					{
						dp[i]=dp[lst[res]]+1;
						from[i]=lst[res];
					}
				}
			}
		}
		if(!lst[name]||dp[lst[name]]<dp[i]) lst[name]=i;
	}
	int ans=0,idx;
	for(int i=1;i<=n;i++)
	{
		if(dp[i]>ans)
		{
			ans=dp[i];
			idx=i;
		}
	}
	cout<<ans<<'\n';
	int now=idx,cnt2=0;
	while(now)
	{
		fans[++cnt2]=now;
		now=from[now];
	}
	for(int i=cnt2;i;i--) cout<<fans[i]<<' ';
	return 0;
}