首页 > 专题系列 > Java解POJ > POJ 1187 陨石的秘密 [解题报告] Java
2013
11-09

POJ 1187 陨石的秘密 [解题报告] Java

陨石的秘密

问题描述 :

公元11380年,一颗巨大的陨石坠落在南极。于是,灾难降临了,地球上出现了一系列反常的现象。当人们焦急万分的时候,一支中国科学家组成的南极考察队赶到了出事地点。经过一番侦察,科学家们发现陨石上刻有若干行密文,每一行都包含5个整数:

1 1 1 1 6

0 0 6 3 57

8 0 11 3 2845

著名的科学家SS发现,这些密文实际上是一种复杂运算的结果。为了便于大家理解这种运算,他定义了一种SS表达式:

1. SS表达式是仅由’{‘,’}',’[',']‘,’(’,’)’组成的字符串。

2. 一个空串是SS表达式。

3. 如果A是SS表达式,且A中不含字符’{‘,’}',’[',']‘,则(A)是SS表达式。

4. 如果A是SS表达式,且A中不含字符’{‘,’}',则[A]是SS表达式。

5. 如果A是SS表达式,则{A}是SS表达式。

6. 如果A和B都是SS表达式,则AB也是SS表达式。

例如

()(())[]

{()[()]}

{{[[(())]]}}

都是SS表达式。



()([])()

[()

不是SS表达式。

一个SS表达式E的深度D(E)定义如下:



例如(){()}[]的深度为2。

密文中的复杂运算是这样进行的:

设密文中每行前4个数依次为L1,L2,L3,D,求出所有深度为D,含有L1对{},L2对[],L3对()的SS串的个数,并用这个数对当前的年份11380求余数,这个余数就是密文中每行的第5个数,我们称之为?神秘数?。

密文中某些行的第五个数已经模糊不清,而这些数字正是揭开陨石秘密的钥匙。现在科学家们聘请你来计算这个神秘数。

输入:

共一行,4个整数L1,L2,L3,D。相邻两个数之间用一个空格分隔。

(0 <= L1 <= 10,0 <= L2 <= 10,0 <= L3 <= 10,0 <= D <= 30)

输出:

共一行,包含一个整数,即神秘数。

样例输入:

1 1 1 2

样例输出:

8

解题代码:

//* @author: 
import java.util.*;
public class Main {
  static int s[][][][]=new int[31][11][11][11];

static int get( int d, int l1, int l2, int l3 )
{
    int t, j, k, i, h;
    
    if( l1 == 0 && l2 == 0 && l3 == 0 && d >= 0 )
    	return 1;
	
 	if( d <= 0 )
    	return 0;
    	
	if( ( t = s[d][l1][l2][l3] ) >= 0 )
		return t;
		
	t = 0;
	
	if( d == 1 )
	{
	    if( l1!=0 ) t += get( d, l1-1, l2, l3 );
	    if( l2!=0 ) t += get( d, l1, l2-1, l3 );
	    if( l3!=0 ) t += get( d, l1, l2, l3-1 );
     	
     	t %= 11380;
      	s[d][l1][l2][l3] =  t;
	    return t ;
	}    
	
 	for( i=0; i<=l1-1; i++ )
	for( j=0; j<=l2; j++ )
 	for( k=0; k<=l3; k++ )
  	{
       	t += ( get( d-1, i, j, k ) * get( d, l1-1-i, l2-j, l3-k ) );
        if( t > ( 1 << 30 ) ) t %= 11380;
    }    
  	
	for( j=0; j<=l2-1; j++ )
	for( k=0; k<=l3; k++ )
	{
     	t += ( get( d-1, 0, j, k ) * get( d, l1, l2-1-j, l3-k ) );
 	 	if( t > ( 1 << 30 ) ) t %= 11380;
   	}  	 
	
	for( k=0; k<=l3-1; k++ )
	{
     	t += ( get( d-1, 0, 0, k ) * get( d, l1, l2, l3-1-k ) );
 	 	if( t > ( 1 << 30 ) ) t %= 11380;
   	}  	 

	t %= 11380;
	s[d][l1][l2][l3] = t;
	
	return t;
}

 public static void main(String[] args){

    Scanner in = new Scanner(System.in);
    int d, l1, l2, l3, i, j, k, l;
      l1=in.nextInt();
      l2=in.nextInt();
      l3=in.nextInt();
      d=in.nextInt();
    
 	for( l=0; l<=d; l++ )
 	for( i=0; i<=l1; i++ )
 	for( j=0; j<=l2; j++ )
 	for( k=0; k<=l3; k++ )
 		s[l][i][j][k] = -1;
	System.out.printf( "%d\n", ( get( d, l1, l2, l3 ) - get( d-1, l1, l2, l3 ) + 11380 ) % 11380 );
	
	}
 }

  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  2. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法