如何创建一个免费网站,蓝色企业网站配色,网络策划案怎么写,虚拟机做的网站怎么让外网访问不了网题干#xff1a;
在过三个礼拜#xff0c;YellowStar有一场专业英语考试#xff0c;因此它必须着手开始复习。
这天#xff0c;YellowStar准备了n个需要背的单词#xff0c;每个单词的长度均为m。
YellowSatr准备采用联想记忆法来背诵这n个单词#xff1a;
1、如果Ye…题干
在过三个礼拜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
3 4 2
abch
abcd
efgh
Sample Output
10
Hint
最优方案是先凭空记下abcd和efgh消耗精力8,在通过abcd联想记忆去背诵abch汉明距离为1,消耗为1 * w 2,总消耗为10。
解题报告 这题巧就巧在字符串是相同长度的所以新开一个单词的代价都是同一个m不然就不好处理了。最后再加上一个起始m就是答案。因为构成了一个完全图所以prim算法肯定更快一些。这里就不管那些了。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e6 5;
int f[MAX];
int n,m,w;
char s[1005][55];
struct Edge {int u,v;int w;
} e[MAX];
bool cmp(Edge a,Edge b) {return a.w b.w;
}
int getf(int v) {return v f[v] ? v : f[v] getf(f[v]);
}
void merge(int u,int v) {int t1 getf(u);int t2 getf(v);f[t2] t1;
}
int hamming(int x,int y) {int res 0;for(int i 0; im; i) {res s[x][i] ! s[y][i]; }return res;
}
int main()
{while(~scanf(%d%d%d,n,m,w)) {int tot 0;for(int i 1; in*n; i) f[i] i;for(int i 1; in; i) scanf(%s,s[i]);for(int i 1; in; i) {for(int j i1; jn; j) {e[tot].u i;e[tot].v j;e[tot].w min(w*hamming(i,j),m);}}int ans 0;sort(e1,etot1,cmp);for(int u,v,i 1; itot; i) {u e[i].u,v e[i].v;if(getf(u) ! getf(v)) {merge(u,v);ans e[i].w;}}printf(%d\n,m ans); }return 0 ;
}
