对ditch里边的单词进行枚举, 需要预处理, 过滤掉不符合题意的单词.
/**//*
ID: lorelei3
TASK: lgame
LANG: C++
*/
#include <fstream>
#include <string>
#include <memory.h>
using namespace std;
const int marks[] = 
{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};
const int MAX = 50000;
struct Word{
string word;
int mark;
int cnt[26];
};
ifstream fin1("lgame.in");
ifstream fin2("lgame.dict");
ofstream fout("lgame.out");
Word words[MAX];
int tot;
string ans[MAX];
int len;
string letters;
int letters_cnt[26];
int maxMark;
int getMark(string s){
int sum=0, len=s.length();
for(int i=0; i<len; ++i)
sum += marks[s[i]-'a'];
return sum;
}
void getCount(string s, int cnt[]){
int len = s.length();
for(int i=0; i<len; ++i)
cnt[s[i]-'a']++;
}
void mergeCount(int cnt1[], int cnt2[], int cnt[]){
for(int i=0; i<26; ++i)
cnt[i] = cnt1[i]+cnt2[i];
}
bool checkCount(int cnt[]){
for(int i=0; i<26; ++i)
if(cnt[i]>letters_cnt[i])
return false;
return true;
}
void init(){
//init letter
fin1>>letters;
getCount(letters, letters_cnt);
//maxlength = letters.length();
//init ditch
string word;
while(fin2>>word && word!="."){
int cnt[26];
memset(cnt, 0, sizeof(cnt));
getCount(word, cnt);
if(checkCount(cnt)){
memcpy(words[tot].cnt, cnt, sizeof(int)*26);
words[tot].word = word;
words[tot].mark = getMark(word);
tot++;
}
}
}
void solve(){
for(int i=0; i<tot; ++i){
if(words[i].mark>maxMark){
maxMark = words[i].mark;
len=0;
ans[len] = words[i].word;
len++;
}else if(words[i].mark == maxMark){
ans[len++] = words[i].word;
}
for(int j=i+1; j<tot; ++j){
int cnt[26];
memset(cnt, 0, sizeof(cnt));
mergeCount(words[i].cnt, words[j].cnt, cnt);
if(!checkCount(cnt))
continue;
if(words[i].mark + words[j].mark > maxMark ){
maxMark = words[i].mark + words[j].mark;
len = 0;
ans[len] = words[i].word+" "+words[j].word;
len++;
}else if(words[i].mark + words[j].mark == maxMark){
ans[len++] = words[i].word+" "+words[j].word;
}
}
}
}
void output(){
fout<<maxMark<<endl;
for(int i=0; i<len; ++i)
fout<<ans[i]<<endl;
}
int main(){
init();
solve();
output();
return 0;
}posted on 2011-01-30 11:23
小阮 阅读(193)
评论(0) 编辑 收藏 引用 所属分类:
USACO