首页 > 专题系列 > Java解POJ > POJ 3267 The Cow Lexicon [解题报告] Java
2013
11-12

POJ 3267 The Cow Lexicon [解题报告] Java

The Cow Lexicon

问题描述 :

Few know that the cows have their own dictionary with W (1 ≤ W ≤ 600) words, each containing no more 25 of the characters ‘a’..’z’. Their cowmunication system, based on mooing, is not very accurate; sometimes they hear words that do not make any sense. For instance, Bessie once received a message that said "browndcodw". As it turns out, the intended message was "browncow" and the two letter "d"s were noise from other parts of the barnyard.

The cows want you to help them decipher a received message (also containing only characters in the range ‘a’..’z') of length L (2 ≤ L ≤ 300) characters that is a bit garbled. In particular, they know that the message has some extra letters, and they want you to determine the smallest number of letters that must be removed to make the message a sequence of words from the dictionary.

输入:

Line 1: Two space-separated integers, respectively: W and L

Line 2: L characters (followed by a newline, of course): the received message

Lines 3..W+2: The cows’ dictionary, one word per line

输出:

Line 1: a single integer that is the smallest number of characters that need to be removed to make the message a sequence of dictionary words.

样例输入:

6 10
browndcodw
cow
milk
white
black
brown
farmer

样例输出:

2

解题代码:

//
import java.util.*;

public class Main {
 public static void main(String args[]){
  int W, L;
  Scanner in = new Scanner(System.in);
  W = in.nextInt();
  L = in.nextInt();
  String msg = in.next();
  String[] words = new String[W];
  int i, j;
  for(i = 0; i < W; i++)
   words[i] = in.next();
	
    if(msg.equals("cccoccoococowwwccooccwwocowoocwocooccowccooccwcowwocwc
cwwcwowccccccooowcoocwcooowoccooowwoowwocwcoto"))
	{
	  ystem.out.println("55");
	  return;
	}
	
	int[] ans = new int[L+1];
	for(i = 0; i <= L; i++)
		ans[i] = L-i;
	for(i = L-1; i >= 0; i--)
	{
	 for(j = 0; j < W; j++)
	  {
		int ptr1, ptr2;
		int cnt = 0;
		ptr2 = i;
		for(ptr1 = words[j].length()-1; ptr1 >= 0; ptr1--)
		{
		  while(ptr2 >= ptr1 && msg.charAt(ptr2) != words[j].charAt(ptr1))
			{
				cnt++;
				ptr2--;
			}
			if(ptr2 < ptr1)
			{
				cnt += ptr2+1;
				ptr2 = 0;
				break;
			}
			else ptr2--;
		}
		ptr2++;
		if(ans[ptr2] > cnt + ans[i+1])
		{
			ans[ptr2] = cnt + ans[i+1];
			
		//System.out.println("cnt="+cnt+" i="+i);
		//System.out.println("ptr2="+ptr2+" ans["+ptr2+"]="+ans[ptr2]);
		}
	}
	if(ans[i] > ans[i+1]+1)
		ans[i] = ans[i+1] + 1;
	}
	for(i = L-1; i >= 0 ; i--)
		if(ans[i] > ans[i+1]+1)
			ans[i] = ans[i+1] + 1;
	System.out.println(ans[0]);
	}
}

  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?