usaco_4_3_4_lgame.cpp

usaco自己做的1到5章的代码

/*
PROB: lgame
LANG: C++
*/
/*
这道题……难得在这一章出现这么简单的题啊。
读懂题意很重要，这道题是说，从lgame.in中读入一行字串，然后在字典中找出一个或一对字串，它(它们)的各个字符数不能超过给定的那个串，比如
program，那么字典找出的字串中只能含有p,r,a,g,o,m.而且，r最多出现两次，其它最多出现一次。
在这些串中，找出字符权值和最大的那些串，按字典序输出即可。
具体做法就是枚举就行了，而且按顺序枚举，最后也不用排序。
在读入dict文件时，可以直接把不符合条件的串去掉，不符合条件的是：
1.串长大于给定串的
2.串中某字母出现次数大于给定串中相同字母的（包括没出现的字母）
*/
#include<iostream>
#include<fstream>
#include<cstring>
#include<algorithm>
#define cin fin
using namespace std;
ifstream fin("lgame.in");
ofstream fout("lgame.out");
struct STR{
	char s[10];
	int len;
	int score;
}str[40000];
int charnum[26]={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 nums[26];
int temp[26],temp2[26];
char s[10];
int cun[40000][2];
int n,m,t,maxs,ptr,maxg=0;

int main()
{
	int i,j,k;
	STR ste;
	memset(nums,0,sizeof(nums));
	memset(cun,-1,sizeof(cun));
	ifstream fdict("lgame.dict");
	fin>>s;
	m=strlen(s);
	for(i=0;i<m;i++) {nums[s[i]-'a']++; maxg+=charnum[s[i]-'a'];}
	i=0;
	while(fdict>>str[i].s)
	{
	    if(str[i].s[0]=='.') break;
		memset(temp,0,sizeof(temp));
		str[i].len=strlen(str[i].s);
		if(str[i].len > m) continue;
		for(j=0;j<str[i].len;j++)
			if(nums[str[i].s[j]-'a']==0)
				{ i--; break;}
			else
			{
				temp[str[i].s[j]-'a']++;
				if(temp[str[i].s[j]-'a']>nums[str[i].s[j]-'a'])
				{i--; break;}
			}
		i++;
	}
	n=i;
	fdict.close();
	maxs=0; ptr=0;
	int sum,sum2;
	for(i=0;i<n;i++)
	{
		memcpy(temp,nums,sizeof(nums));
		sum=0;
		for (j=0;j<strlen(str[i].s);j++)
		{
			sum+=charnum[str[i].s[j]-'a'];
			temp[str[i].s[j]-'a']--;
		}
		if(sum>maxs) {maxs=sum; ptr=0; cun[ptr][0]=i;}
		else if(sum==maxs) {cun[++ptr][0]=i;cun[ptr][1]=-1;}
		if(sum==maxg) continue;
		for(j=i+1;j<n;j++)
		{
		    memcpy(temp2,temp,sizeof(temp));
		    sum2=sum;
			if(str[i].len+str[j].len > m) continue;
			for (k=0;k<strlen(str[j].s);k++)
			{
				sum2+=charnum[str[j].s[k]-'a'];
				temp2[str[j].s[k]-'a']--;
			}
			t=1;
			for(k=0;k<26;k++) if(temp2[k]<0) t=0;
			if(t==0) continue;
			if(sum2>maxs) {maxs=sum2; ptr=0; cun[ptr][0]=i; cun[ptr][1]=j;}
			else if(sum2==maxs) {cun[++ptr][0]=i; cun[ptr][1]=j;}
		}
	}
	fout<<maxs<<endl;
	for(i=0;i<=ptr;i++)
		if(cun[i][1]==-1) fout<<str[cun[i][0]].s<<endl;
		else fout<<str[cun[i][0]].s<<' '<<str[cun[i][1]].s<<endl;
	return 0;
}