|
思路:
它的要求是,给你几个字母,用这些字母拼几个字典里面有的单词,所有单词加起来求最高得分。 转化一下,就是个01背包问题。 由于单词的长度很短很短了,只有3~7个字母,所以总状态数很少啦。数组开到 2048 就可以AC了。
后来又搜了一下别人的解题报告哦,发现有个哥们很牛逼。 他说:单词长度范围在3--7内。所以可能的词组 只能是 3+3 或 3+4
一语惊醒脑残人。太牛逼了! 代码 150ms AC。
#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; }
|