Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
80题Mark一下……还有我写得很渣的代码,不要直接抄哦,可能会错/* * POJ 1171 Letter Game * ------------------------ * This program can get highest points by generate words * using the letters given in the letter box */ #include<cstdio> #include<cstring> #include<vector> using namespace std; //value box const int nScore[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}; const int MAX = 40002; int nMaxScore = 0; int nWordNum = 0; //Define a class to store the num of letters used class WordBox{ public: WordBox():score(0){memset(m_num,0,26 * sizeof(int));} void Init(const char* ch){ score = 0; memset(m_num,0,26 * sizeof(int)); for(int i = 0;ch[i];++i){ ++m_num[ch[i] - 'a']; score += nScore[ch[i] - 'a']; } } //See if the word can be created by letterbox bool operator > (const WordBox& m){ for(int j = 0;j < 26;++j){ if(m_num[j] < m.m_num[j])return false; }return true; } //Add up two words WordBox operator + (const WordBox& m){ WordBox a; a.score = score + m.score; for(int i = 0;i < 26;++i)a.m_num[i] = m_num[i] + m.m_num[i]; return a; } int Avalible(){ int i = 0; for(int j = 0;j < 26;++j){ i += m_num[j]; } return i; } int score; private: int m_num[26]; }LetterBox,temp0; vector<WordBox> Word; typedef vector<WordBox>::iterator pWord; void dfs(){ const pWord start = Word.begin(),end = Word.end(); pWord i,j; for(i = start;i != end;++i){ for(j = i + 1;j != end;++j){ //Pruning 1:only check pair may exceeded nMaxScore if(nMaxScore < i->score + j->score){ WordBox temp0 = *i + *j; if(LetterBox > temp0) nMaxScore = temp0.score; } } } } int main(){ char str[8] = {0}; scanf("%s",str); LetterBox.Init(str); for(;;){ scanf("%s",str); if(str[0] == '.')break; temp0.Init(str); //Pruning 2.Only suitable words are recorded if(LetterBox > temp0){ //Single word Word.push_back(temp0); if(temp0.score > nMaxScore) nMaxScore = temp0.score; } } //Check all possible combinations dfs(); printf("%d\n",nMaxScore); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator