Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

80题Mark一下……还有我写得很渣的代码,不要直接抄哦,可能会错

Posted by 1200017623 at 2013-02-06 19:33:42 on Problem 1171
/*
 * 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator