自动搬运

查看原文

来自洛谷，原作者为

	Celebrate 观千剑而后识器

搬运于2025-08-24 21:41:11，当前版本为作者最后更新于2018-05-19 09:20:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这一道题也没有什么算法了，就是纯靠思维来做的

在输入的字母之中，有很多个都是不行的（或超出范围的），

所以我们只用记录可以用的单词

找完可以用的单词，就用两重for循环找出最大值并且直接

记录，最后输出就可以了，把小写字母a,b,c,d变成1,2,3,4 就是

ss[]-'a'+1

代码如下：

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int x,y;//记录最大值，x记录被选单词的序号，如果y是0，就只有x一个 
}result[5100];int len,maxx=0;
struct node1
{
	char s[11];
	int len,score;//记录单词 
}st[5100];int n;
char ss[31];
const int s[27]={0,2,5,4,4,1,6,5,5,1,7,6,3,5,2,3,5,7,2,1,2,4,6,6,7,5,7};//分值 
int flag[31];//flag记录每个字母最多可以出现多少次 
bool pd()//判断这一个是否可以 
{
	int i,k[31];memset(k,0,sizeof(k));
	for(i=1;i<=strlen(ss+1);i++)
	{
		k[ss[i]-'a'+1]++;
		if(k[ss[i]-'a'+1]>flag[ss[i]-'a'+1]) return false;//如果超出范围，就肯定不可以了 
	}
	return true;
}
bool check(int x,int y)//判断两个加起来是否超出范围 
{
	int i,k[31];memset(k,0,sizeof(k));
	for(i=1;i<=st[x].len;i++)
	{
		k[st[x].s[i]-'a'+1]++;
		if(k[st[x].s[i]-'a'+1]>flag[st[x].s[i]-'a'+1]) return false;
	}
	for(i=1;i<=st[y].len;i++)
	{
		k[st[y].s[i]-'a'+1]++;
		if(k[st[y].s[i]-'a'+1]>flag[st[y].s[i]-'a'+1]) return false;
	}
	return true;
}
int main()
{
	int i,j;
	scanf("%s",ss+1);
	for(i=1;i<=strlen(ss+1);i++) flag[ss[i]-'a'+1]++;//记录 
	while(scanf("%s",ss+1)!=EOF)
	{
		if(ss[1]=='.') break;//如果输入到句号，就推出 
		if(pd()==true)//如果这个单词没有超出范围 
		{
			n++;
			st[n].len=strlen(ss+1);
			for(i=1;i<=st[n].len;i++)//把这个单词记录下来 
			{
				st[n].s[i]=ss[i];
				st[n].score=st[n].score+s[ss[i]-'a'+1];//分值 
			}
		}
	}
	for(i=1;i<=n;i++)
	{
		if(st[i].score>maxx)//先找单独一个单词，如果超过分值 
		{
			len=1;//重置并且记录 
			result[1].x=i;
			maxx=st[i].score;
		}
		else if(st[i].score==maxx)//如果等于最大值 
		{
			len++;//增加一个 
			result[len].x=i;
		}
		for(j=i;j<=n;j++)//找后面的（包括自己，因为一个单词可以用两次） 
		{
			if(check(i,j)==true)//如果可以 
			{
				if(st[i].score+st[j].score>maxx)//更新最大值 
				{
					len=1;result[1].x=i;result[1].y=j;
					maxx=st[i].score+st[j].score;
				}
				else if(st[i].score+st[j].score==maxx)
				{
					len++;result[len].x=i;result[len].y=j;
				}
			}
		}
	}
	printf("%d\n",maxx);//直接输出，因为已经按照字典序排好了，没有必要再排一次 
	for(i=1;i<=len;i++)//输出 
	{
		for(j=1;j<=st[result[i].x].len;j++) printf("%c",st[result[i].x].s[j]);
		if(result[i].y>0)
		{
			printf(" ");
			for(j=1;j<=st[result[i].y].len;j++) printf("%c",st[result[i].y].s[j]);
		}
		printf("\n");
	}
	return 0;
}