糯米

思路：

它的要求是，給你幾個(gè)字母，用這些字母拼幾個(gè)字典里面有的單詞，所有單詞加起來(lái)求最高得分。
轉(zhuǎn)化一下，就是個(gè)01背包問(wèn)題。
由于單詞的長(zhǎng)度很短很短了，只有3~7個(gè)字母，所以總狀態(tài)數(shù)很少啦。數(shù)組開(kāi)到 2048 就可以AC了。

后來(lái)又搜了一下別人的解題報(bào)告哦，發(fā)現(xiàn)有個(gè)哥們很牛逼。
他說(shuō)：單詞長(zhǎng)度范圍在3--7內(nèi)。所以可能的詞組 只能是 3+3 或 3+4

#include <stdio.h>

char key[] = {
    "qwertyuiop"
    "asdfghjkl"
    "zxcvbnm"
};
int score[] = {
    7, 6, 1, 2, 2, 5, 4, 1, 3, 5,
    2, 1, 4, 6, 5, 5, 7, 6, 3,
    7, 7, 4, 6, 5, 2, 5
};

int map[256], col[256], idx[256], mul[8], tot[8], cnt, hash[2048], top;

int can_add(int a, int b)
{
    int i, ia, ib;

    for (i = 1; i < cnt; i++) {
        ia = (a / mul[i - 1]) % tot[i];
        ib = (b / mul[i - 1]) % tot[i];
        if (ia + ib >= tot[i])
            return 0;
    }

    return 1;
}

int main()
{
    int i, val, sum[256], sc;
    char str[16];

    freopen("e:\\test\\in.txt", "r", stdin);

    for (i = 0; i < 26; i++)
        map[key[i]] = score[i];
    
    scanf("%s", str);
    for (i = 0; str[i]; i++)
        col[str[i]]++;

    cnt = 1;
    for (i = 'a'; i <= 'z'; i++)
        if (col[i]) {
            idx[i] = cnt;
            mul[cnt] = tot[cnt] = col[i] + 1;
            cnt++;
        }

    mul[0] = 1;
    for (i = 1; i < cnt; i++)
        mul[i] *= mul[i - 1];
    top = mul[cnt - 1];
    hash[0] = 1;

    while (scanf("%s", str), str[0] != '.') {
        for (i = 'a'; i <= 'z'; i++)
            sum[i] = 0;
        sc = 0;
        val = 0;
        for (i = 0; str[i]; i++) {
            sum[str[i]]++;
            if (sum[str[i]] > col[str[i]])
                break;
            sc += map[str[i]];
            val += mul[idx[str[i]] - 1];
        }
        if (str[i])
            continue;
        for (i = top; i >= 0; i--) {
            if (!hash[i])
                continue;
            if (can_add(i, val) && hash[i + val] < hash[i] + sc)
                hash[i + val] = hash[i] + sc;
        }
    }

    sc = 0;
    for (i = top; i >= 0; i--)
        if (hash[i] > sc)
            sc = hash[i];
    printf("%d\n", sc - 1);

    return 0;
}