本文主要是介绍FZU 2254 英语考试，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Accept: 88 Submit: 218 Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
在过三个礼拜，YellowStar有一场专业英语考试，因此它必须着手开始复习。
这天，YellowStar准备了n个需要背的单词，每个单词的长度均为m。
YellowSatr准备采用联想记忆法来背诵这n个单词：
1、如果YellowStar凭空背下一个新词T，需要消耗单词长度m的精力
2、如果YellowSatr之前已经背诵了一些单词，它可以选择其中一个单词Si，然后通过联想记忆的方法去背诵新词T，需要消耗的精力为hamming(Si, T) * w。
hamming(Si, T)指的是字符串Si与T的汉明距离，它表示两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。
由于YellowStar还有大量繁重的行政工作，因此它想消耗最少的精力背诵下这n个单词，请问它最少需要消耗多少精力。
Input
包含多组测试数据。
第一行为n, m, w。
接下来n个字符串，每个字符串长度为m，每个单词均为小写字母'a'-'z'组成。
1≤n≤1000
1≤m, w≤10
Output
输出一个值表示答案。
Sample Input
Sample Output
Hint
最优方案是：先凭空记下abcd和efgh消耗精力8,在通过abcd联想记忆去背诵abch，汉明距离为1,消耗为1 * w = 2,总消耗为10。
类似于poj1789，我们可以新建一个根结点，根结点到所有单词的花费均为m，每个单词之间的花费为联想记忆的花费，直接上prim即可。
Source
福州大学第十四届程序设计竞赛_重现赛
#include <cstdio>
#include <cstring>
#include <algorithm>
#define QAQ 0x3f3f3f3f
#define LDQ 1000000007
using namespace std;
int mp[1001][1001];
int f(char s[],char s1[],int w)
{int i,sum=0;for(i=0;s[i]!='\0';i++){if(s[i]!=s1[i]){sum=sum+w;}}return sum;
}
int prim(int n)
{int sum=0,v[1001],dis[1001],i,i1,t,pos;memset(dis,QAQ,sizeof(dis));memset(v,0,sizeof(v));dis[n]=0;for(i=0;n>=i;i++){t=QAQ;for(i1=0;n>=i1;i1++){if(v[i1]==0&&t>dis[i1]){t=dis[i1];pos=i1;}}sum=sum+t;v[pos]=1;for(i1=0;n>=i1;i1++){if(v[i1]==0&&dis[i1]>mp[pos][i1]){dis[i1]=mp[pos][i1];}}}return sum;
}
int main()
{int n,m,w,i,i1;char s[1000][1001];while(scanf("%d %d %d",&n,&m,&w)!=EOF){for(i=0;n>i;i++){scanf("%s",s[i]);}for(i=0;n>i;i++){for(i1=i+1;n>i1;i1++){mp[i][i1]=mp[i1][i]=f(s[i],s[i1],w); //每个单词之间建边}}for(i=0;n>i;i++) //建立根结点，根结点到每个单词的花费均为m{mp[n][i]=mp[i][n]=m;}printf("%d\n",prim(n));}return 0;
}这篇关于FZU 2254 英语考试的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
