Letter Game

題意：不想寫，摘抄NOCOW翻譯（http://www.nocow.cn/index.php/Translate:USACO/lgame）

描述

在家裡用電視機做字母遊戲是很流行的，其中一種玩法是:每一個字母有一個數值與之對應.你收集字母組成一個或多個詞以得到盡可能高的得分.除非你已有了 “找詞的方法”(“a way with words”)，你會把你知道的字都試一遍.有時你也許會查閱其拼寫，然後計算得分。顯然可以用計算機更為準确地完成此任務。上圖示出了英文字母及其所對應的值，當給出英文單詞(word) 的表列及收集的字母時，請找出所能形成的得分最高的詞或詞對(pairs of words)。

[編輯]格式

PROGRAM NAME: lgame

INPUT FORMAT:

(file lgame.in)

輸入檔案lgame.in中有一行由小寫字母(`a'到`z')組成的字元串， 這就是收集到字母(就是可以使用的字母)，字元串由至少3個字母至多7個字母(以任意順序) 組成。

(file lgame.dict)

詞典檔案lgame.dict由至多40，000行組成，檔案的最後一行有'.' 表示檔案的結束。其它各行每一行都是由至少3個小寫字母，至多7 個小寫字母組成的字元串。檔案中的詞已按字典順序排序。

OUTPUT FORMAT:

(file lgame.out)

在檔案lgame.out的第一行，你的程式應寫上最高得分(子任務A).使用上面圖形中給出的字母-值對應表。

随後的每一行是由檔案lgame.dict中查到的具有這個得分的所有的詞和或詞對(word pairs)(子任務B)。要利用圖中給定的字母的值。

當兩個詞能夠形成 一個組合(具有給定的字母)時，這兩個詞應該列印到同一行，兩個詞中間用一個空格隔開。不許重複表示詞對，例如'rag prom'和'prom rag'是同樣的詞對，隻輸出字典順序較小的那個。

輸出要按照字典順序排序，如果兩個詞對第一個單詞的順序相同，則按照第二個單詞。一個詞對中的兩個單詞可以相同。

[編輯]SAMPLE INPUT(file lgame.in)

prmgroa
      

[編輯]SAMPLE INPUT(file lgame.dict)

profile
program
prom
rag
ram
rom
.
      

[編輯]SAMPLE OUTPUT

24
program
prom rag      

解題思路：

1. 讀字典檔案，将滿足條件（每種字母的個數不超過輸入序列中每個字母個數）的單詞儲存下來，存與diction中，diction_num儲存diction的條數
2. 對單個單詞，順序列舉一遍diction就能進行處理
3. 對兩個單詞，用兩層循環來列舉diction中選取兩個單詞的所有可能（i = [0, diction_num)，j = [i, diction_num)）
4. 在列舉過程中更新最高得分，并且存儲相應的單詞和詞組，最後得到的結果輸出即可

代碼：

/*
ID: zc.rene1
LANG: C
PROG: lgame
 */

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct unit
{
    int letter[26];
    char str[8];
    int score;
};

struct unit diction[40000];
int diction_num = 0;
int SCORE[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 in[26];

char result[10000][10];
int result_num = 0;

void GetInput(FILE *fin)
{
    char str[8];
    int i;
    
    memset(in, 0, 26 * sizeof(int));
    memset(str, 0, 8 * sizeof(char));
    fscanf(fin, "%s", str);

    for (i=0; i<strlen(str); i++)
    {
	in[str[i] - 'a']++;
    }
}

int GetScore(const int *letter)
{
    int i, sum = 0;

    for (i=0; i<26; i++)
    {
	if (letter[i] > in[i])
	{
	    return -1;
	}
	sum += letter[i] * SCORE[i];
    }
    return sum;
}

void GetDict(FILE *dict)
{
    char str[8];
    int i, sc;
    int letter[26];

    while (1)
    {
	fscanf(dict, "%s", str);
	if (str[0] == '.')
	{
	    break;
	}

	memset(letter, 0, 26 * sizeof(int));

	for (i=0; i<strlen(str); i++)
	{
	    letter[str[i] - 'a']++;
	}
	sc = GetScore(letter);
	if (sc != -1)
	{
	    memcpy(diction[diction_num].letter, letter, 26 * sizeof(int));
	    memcpy(diction[diction_num].str, str, 8 * sizeof(char));
	    diction[diction_num].score = sc;
	    diction_num++;
	}
    }
}

int GetResult(void)
{
    int i, j, k;
    int sc1, sc2, sc;
    int max = -1;
    int lt[26];

    for (i=0; i<diction_num; i++)
    {
	sc = diction[i].score;
	if (sc > max)
	{
	    memset(result, 0, 10000 * 10 * sizeof(char));
	    max = sc;
	    result_num = 0;
	    strcpy(result[result_num], diction[i].str); 
	    result_num++;
	}
	else if (sc == max)
	{
	    strcpy(result[result_num], diction[i].str);
	    result_num++;
	}

	for (j=i; j<diction_num; j++)
	{
	    for (k=0; k<26; k++)
	    {
		lt[k] = diction[i].letter[k] + diction[j].letter[k];
	    }
	    sc = GetScore(lt);

	    if (sc > max)
	    {
		memset(result, 0, 10000 * 10 * sizeof(char));
		max = sc;
		result_num = 0;
		strcpy(result[result_num], diction[i].str);
		result[result_num][strlen(diction[i].str)] = ' ';
		strcat(result[result_num], diction[j].str);
		result_num++;
	    }
	    else if (sc == max)
	    {
		strcpy(result[result_num], diction[i].str);
		result[result_num][strlen(diction[i].str)] = ' ';
		strcat(result[result_num], diction[j].str);
		result_num++;
	    }
	}
    }

    return max;
}

int main(void)
{
    FILE *fin, *fout, *dict;
    int i, max;

    fin = fopen("lgame.in", "r");
    dict = fopen("lgame.dict", "r");
    fout = fopen("lgame.out", "w");

    GetInput(fin);
    GetDict(dict);
    max = GetResult();

    fprintf(fout, "%d\n", max);
    for (i=0; i<result_num; i++)
    {
	fprintf(fout, "%s\n", result[i]);
    }
    return 0;
}