首页 > 专题系列 > Java解POJ > POJ 1171 Letter Game [解题报告] Java
2013
11-09

POJ 1171 Letter Game [解题报告] Java

Letter Game

问题描述 :



Figure 1:Each of the 26 lowercase letters and its value

Letter games are popular at home and on television. In one version of the game, every letter has a value, and you collect letters to form one or more words giving the highest possible score. Unless you have ‘a way with words’, you will try all the words you know, sometimes looking up the spelling, and then compute the scores. Obviously, this can be done more accurately by computer.

Given the values in Figure 1, a list of English words, and the letters collected: find the highest scoring words or pairs of words that can be formed,in which a letter must not occur more often than in the collected letters.

输入:

Your program is to read from standard input. The first line contains a string of lowercase letters (from ‘a’ to ‘z’): the letters collected. The string consists of at least 3 and at most 7 letters in arbitrary order.

From the second line, there is a dictionary consisting of at most 40,000 lines. At the end of the dictionary is a line with a single period (‘.’). Each of the other lines contains a string of at least 3 and at most 7 lowercase letters. The dictionary is sorted alphabetically and contains no duplicates.

输出:

Your program is to write to standard output. You should output one line with the highest score.

样例输入:

prmgroa
profile
program
prom
rag
ram
rom
.

样例输出:

24

温馨提示:

Huge input,scanf is recommended.

解题代码:

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
public class Main {
 static final int N = 1000+10;
 static int top,ans;
 static String opt = new String();
 static String str[] =new String[N];
 static int score[]={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};
	
 public static void main(String[]args)throws Exception{
	
  top = ans = 0;
	
  StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	
  opt = next_string(cin);
	
  while(true){
	str[top] = next_string(cin);
	if(str[top].equals(".")) break;
	if(can_save(opt,str[top])) {
			
          ans = Max(ans,get_score(str[top]));
	  ++top;
	}
   }
  for(int i=0;i< top;++i){
	for(int j=i+1;j< top;++j){
		str[top+1] = add(str[i],str[j]);
		if(can_save(opt,str[top+1])){
			ans = Max(ans,get_score(str[top+1]));
		}
	}
  }
  System.out.println(ans);
		
 }
	static String add(String obj1,String obj2){
		char temp[] = new char[20];
		String cnt = obj1+obj2;
		temp = cnt.toCharArray();
		Arrays.sort(temp,0,cnt.length());
		
		return String.valueOf(temp);
		
	}
	static int get_score(String op1){
		int i,cnt=0,n=op1.length();
		for(i=0;i< n;++i){
			cnt+=score[(int)(op1.charAt(i)-'a')];
		}
		return cnt;
	}
	static int Max(int a,int b){
		return a>b?a:b;
	}
	static boolean can_save(String op1,String op2){
		
		int i=0,j=0,n =op1.length(),m=op2.length();
		while(i< n && j< m){
			if(op1.charAt(i)==op2.charAt(j)){
				++i;++j;
			}else{
				++i;
			}
		}
		if(j< m) return false;
		
		return true;
	}
	static String next_string(StreamTokenizer cin) throws Exception{
		char temp[] = new char[10];
		String cnt = new String();
		cin.nextToken();
		cnt = cin.sval;
		if(cnt==null) return ".";
		temp = cnt.toCharArray();
		Arrays.sort(temp,0,cnt.length());

		return String.valueOf(temp);
		

	}
}

  1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  2. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }