3065394_ac_460ms_460k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>

using namespace std;

struct node
{
	char words[8];
}dic[40001], first, sub[200];

int sn, ans, high, avi[200];
int l, num, mark[8];
int score[] = {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};

bool cmp(node a,node b)
{
	return strcmp(a.words,b.words)<0;
}

int cmp1(const void *a,const void *b)
{
	struct node *aa = (struct node *)a;
	struct node *bb = (struct node *)b;

	return strcmp(aa->words,bb->words);
}

int get_score(char str[])
{
	int i, ret (0);

	for (i = 0; str[i]; i++)
	{
		ret += score[str[i]-'a'];
	}
	return ret;
}

void solve()
{
	int i;
	int aa;
	char a[8];

	aa = 0;
	for (i = 0; i < l; i++)
	{
		if (mark[i]==1)
		{
			a[aa++] = first.words[i];
		}
	}
	a[aa] = '\0';
	strcpy(sub[sn].words,a);
	sn++;
}

void get(int p,int n)
{
	int i;

	if (n==0)
	{
		solve();
		return ;
	}
	for (i = p; i <= l-n; i++)
	{
		mark[i] = 1;
		get(i+1,n-1);
		mark[i] = 0;
	}
}

int main()
{
	int i, j;

	scanf("%s",first.words);
	high = get_score(first.words);
	l = strlen(first.words);
	sort(first.words,first.words+l);
	num = 0;
	while (scanf("%s",dic[num].words)==1)
	{
		if (dic[num].words[0]=='.')
		{
			break;
		}
		sort(dic[num].words,dic[num].words+strlen(dic[num].words));
		num++;
	}
	sort(dic,dic+num,cmp);
	if (bsearch(first.words,dic,num,sizeof(dic[0]),cmp1)!=NULL)
	{
		printf("%d\n",high);
		return 0;
	}
	ans = -1;
	sn = 0;
	for (i = 1; i < l; i++)
	{
		memset(mark,0,sizeof(mark));
		get(0,i);
	}
	memset(avi,0,sizeof(avi));
	strcpy(sub[sn++].words,first.words);
	sort(sub,sub+sn,cmp);
	for (i = 0; i < sn; i++)
	{
		if (bsearch(sub[i].words,dic,num,sizeof(dic[0]),cmp1)!=NULL)
		{
			avi[i] = 1;
			int tt = get_score(sub[i].words);
			if (tt > ans)
			{
				ans = tt;
			}
		}
	}
	for (i = 0; i < sn-1; i++)
	{
		for (j = i+1; j < sn-1; j++)
		{
			if (strlen(sub[i].words)+strlen(sub[j].words) > l || avi[i]==0 || avi[j]==0)
			{
				continue;
			}
			strcpy(first.words,sub[i].words);
			strcat(first.words,sub[j].words);
			sort(first.words,first.words+strlen(first.words));
			if (bsearch(first.words,sub,sn,sizeof(sub[0]),cmp1)!=NULL)
			{
				int tt = get_score(first.words);
				if (tt > ans)
				{
					ans = tt;
				}
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}