Problem 2254 英語考試

Accept: 35????Submit: 72
Time Limit: 1000 mSec????Memory Limit : 32768 KB

Problem Description

在過三個禮拜，YellowStar有一場專業(yè)英語考試，因此它必須著手開始復(fù)習(xí)。

這天，YellowStar準(zhǔn)備了n個需要背的單詞，每個單詞的長度均為m。

YellowSatr準(zhǔn)備采用聯(lián)想記憶法來背誦這n個單詞：

1、如果YellowStar憑空背下一個新詞T，需要消耗單詞長度m的精力

2、如果YellowSatr之前已經(jīng)背誦了一些單詞，它可以選擇其中一個單詞Si，然后通過聯(lián)想記憶的方法去背誦新詞T，需要消耗的精力為hamming(Si, T) * w。

hamming(Si, T)指的是字符串Si與T的漢明距離，它表示兩個等長字符串之間的漢明距離是兩個字符串對應(yīng)位置的不同字符的個數(shù)。

由于YellowStar還有大量繁重的行政工作，因此它想消耗最少的精力背誦下這n個單詞，請問它最少需要消耗多少精力。

Input

?

包含多組測試數(shù)據(jù)。

第一行為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

最優(yōu)方案是：先憑空記下abcd和efgh消耗精力8,在通過abcd聯(lián)想記憶去背誦abch，漢明距離為1,消耗為1 * w = 2,總消耗為10。

Source

福州大學(xué)第十四屆程序設(shè)計競賽_重現(xiàn)賽? //沒想到額,是最小生成樹，首先想到的竟然是貪心解決，后來發(fā)現(xiàn)這樣顯然錯誤，決定哪些直接記住的很關(guān)鍵。 對于每個單詞，可以直接記憶，也可以通過任何一個單詞聯(lián)想記憶，所以，想到這，可以想到似乎是個完全圖，邊的值為min(m,hamming(Si, T)*w) 然后就跑最小生成樹 kruskal 1 #include <stdio.h> 2 #include <iostream> 3 #include <string.h> 4 #include <algorithm> 5 #include <queue> 6 using namespace std; 7 #define INF 0x3f3f3f3f 8 #define MX 1005 9 struct Node 10 { 11 int u,v; 12 int d; 13 bool operator < (const Node &b)const{ 14 return d>b.d; 15 } 16 }; 17 int n,m,w; 18 char str[MX][15]; 19 priority_queue<Node> Q; 20 int f[MX]; 21 22 int find_h(int x){ 23 if (x!=f[x]) 24 f[x]=find_h(f[x]); 25 return f[x]; 26 } 27 28 void krus() 29 { 30 for (int i=0;i<n;i++) 31 f[i]=i; 32 int res = m; //star at 0 33 int num=1; 34 while (!Q.empty()) 35 { 36 Node tp = Q.top(); 37 Q.pop(); 38 int x=find_h(tp.u),y=find_h(tp.v); 39 if (x!=y) 40 { 41 res+=tp.d; 42 f[x]=y; 43 num++; 44 } 45 if (num==n) break; 46 } 47 printf("%d\n",res); 48 } 49 50 int main() 51 { 52 while (scanf("%d%d%d",&n,&m,&w)!=EOF) 53 { 54 for (int i=0;i<n;i++) 55 scanf("%s",str[i]); 56 while (!Q.empty()) Q.pop(); 57 for (int i=0;i<n;i++) 58 { 59 for (int j=i+1;j<n;j++) 60 { 61 if (i==j) continue; 62 int cp=0; 63 for (int k=0;k<m;k++) 64 if (str[i][k]!=str[j][k]) 65 cp++; 66 Q.push((Node){i,j,min(m,cp*w)}); 67 } 68 } 69 krus(); 70 } 71 return 0; 72 } View Code

?

prim

1 #include <stdio.h> 2 #include <iostream> 3 #include <string.h> 4 #include <algorithm> 5 #include <queue> 6 using namespace std; 7 #define INF 0x3f3f3f3f 8 #define MX 1005 9 struct Node 10 { 11 int u,v; 12 int d; 13 bool operator < (const Node &b)const{ 14 return d>b.d; 15 } 16 }; 17 int n,m,w; 18 char str[MX][15]; 19 int G[MX][MX]; 20 int vis[MX]; 21 int dis[MX]; 22 23 void prim() 24 { 25 memset(vis,0,sizeof(vis)); 26 vis[0]=1; 27 for (int i=0;i<n;i++) 28 dis[i]=G[0][i]; 29 int num=1,sp=m; 30 while (num<n) 31 { 32 int mim=INF,dex; 33 for (int i=0;i<n;i++) 34 if (!vis[i]&&dis[i]<mim) 35 { 36 dex=i; 37 mim=dis[i]; 38 } 39 vis[dex]=1; 40 sp+=mim; 41 num++; 42 for (int i=0;i<n;i++) 43 if (!vis[i]&&dis[i]>G[dex][i]) 44 dis[i]=G[dex][i]; 45 } 46 printf("%d\n",sp); 47 } 48 49 int main() 50 { 51 while (scanf("%d%d%d",&n,&m,&w)!=EOF) 52 { 53 for (int i=0;i<n;i++) 54 scanf("%s",str[i]); 55 for (int i=0;i<n;i++) 56 { 57 for (int j=0;j<n;j++) 58 { 59 if (i==j) continue; 60 int cp=0; 61 for (int k=0;k<m;k++) 62 if (str[i][k]!=str[j][k]) 63 cp++; 64 G[i][j]=G[j][i]=min(m,cp*w); 65 } 66 } 67 prim(); 68 } 69 return 0; 70 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/haoabcd2010/p/7190797.html

超強干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的英语考试(最小生成树)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。