题解 P2753 【[USACO4.3]字母游戏Letter Game】
这一道题也没有什么算法了，就是纯靠思维来做的
在输入的字母之中，有很多个都是不行的（或超出范围的），
所以我们只用记录可以用的单词
找完可以用的单词，就用两重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;
}