最多只有两个字符串参与构成，可以暴力解:
#include <iostream>
using namespace std;
char s[16];
int cnt[256];
int tot[256];
int m[256];
struct DICT
{char words[10];int len,val;
}dic[40010];int tovalue(char ch[])
{int sum=0;for(int i=0;ch[i]!='\0';++i)sum+=m[ch[i]];return sum;
}int add(int list[],char ch[])
{for(int i=0;ch[i]!='\0';++i){++list[ch[i]];if(list[ch[i]]>tot[ch[i]])return false; } return true;
}int main()
{m['q']=7;m['w']=6;m['e']=1;m['r']=2;m['t']=2;m['y']=5;m['u']=4;m['i']=1;m['o']=3;m['p']=5;m['a']=2;m['s']=1;m['d']=4;m['f']=6;m['g']=5;m['h']=5;m['j']=7;m['k']=6;m['l']=3;m['z']=7;m['x']=7;m['c']=4;m['v']=6;m['b']=5;m['n']=2;m['m']=5;int ans=0;scanf("%s",s);for(int i='a';i<='z';++i)tot[i]=0;for(int i=0;s[i]!='\0';++i)++tot[s[i]];int s_len=strlen(s);int dic_index=0;while(scanf("%s",s)==1&&s[0]!='.'){for(int i='a';i<='z';++i)cnt[i]=0;int v=tovalue(s);int len=strlen(s);if(add(cnt,s)==1)ans=max(ans,v);if((s_len==6&&len==3)||(s_len==7&&len<=4)){strcpy(dic[dic_index].words,s);dic[dic_index].len=len;dic[dic_index].val=v;++dic_index;}}if(s_len>=6){for(int i=0;i<dic_index;++i)for(int j=i+1;j<dic_index;++j){for(int k='a';k<='z';++k)cnt[k]=0;if(!add(cnt,dic[i].words))continue;if(!add(cnt,dic[j].words))continue;ans=max(ans,dic[i].val+dic[j].val);}} printf("%d",ans);return 0;
}
</pre><pre name="code" class="cpp">如果多个字符串参与构成，用字符串哈希(或者说字符串压缩为整数，字符串编码)+01背包，将每个字符串用哈希函数映射成体积，参与背包。
<pre name="code" class="cpp">//from internet
#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];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;
}