| ||||||||||
| 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