首页 > 专题系列 > Java解POJ > POJ 3088 Push Botton Lock [解题报告] Java
2013
11-12

POJ 3088 Push Botton Lock [解题报告] Java

Push Botton Lock

问题描述 :

The Frobozz Magic Lock Company is in the business of manufacturing push button style combination door locks. A push button door lock consists of a number of push buttons B, (1 ≤ B ≤ 11), labeled “1” through “B”. The lock is opened by pressing the correct sequence of button combinations and then turning the doorknob. If the sequence of presses is correct, the door magically opens.

A combination consists of 1 or more buttons being pressed simultaneously. A sequence consists of a series of combinations. A sequence must have at least one combination. Once a button has been used in a combination, it may not be used again in the same sequence. In addition, it is not necessary to use all the buttons in a sequence. For example, for B = 8:

(1-2-3)(4)(7-8)

is a valid sequence with 3 combinations (1-2-3), (4), and (7-8). Note that buttons 5 and 6 are not used in this sequence.

(1-2-3)(2-4)(5-6)

is not a valid sequence, since button 2 appears in 2 combinations (1-2-3) and (2-4).

The CEO of Frobozz, J. Pierpont Flathead, wants you to write a program that determines the number of valid sequences possible for given values of B. The program must be able to process a list of lock orders (datasets) from customers and generate a report showing the order number, the value of B, and the number of valid sequences possible. This list will always contain at least one dataset, but no more than 100 datasets.

Reference Materials:


J. Pierpont Flathead

输入:

The first line of input contains a single integer N, (1 ≤ N ≤ 100), representing the number of datasets that follow. Each dataset consists of a single line of data containing a single integer B, which is the number of buttons for the lock.

输出:

For each dataset, display the dataset number, a blank, the value B, a blank, and the number of valid sequences.

样例输入:

3
3
4
3

样例输出:

1 3 25
2 4 149
3 3 25

解题代码:

/* @author: */
import java.util.*;
import java.io.*;
import java.lang.reflect.Array;

public class Main {
  static int a[][] = new int[12][12];
  static long ans[] = new long[12];
	
  static public void main( String [] str ) throws Exception{
    int n;
    int m;
    Scanner cin = new Scanner( System.in );
    n = cin.nextInt();
		
    a[1][1] = 1;
    a[1][0] = 1;
    for( int i=2; i<=11; i++ ) {
     for( int j=1; j<=i; j++ )
	for( int k=1; k< i; k++ )
	  a[i][j] += a[k][j]*j+a[k][j-1]*j;
    }
	
    for( int i=1; i<=11; i++ ) {
      ans[i] = ans[i-1];
      for( int j=1; j<=i; j++ )
	 ans[i] += a[i][j];
    }
		
    for( int k=1; k<=n; k++ ) {
	m = cin.nextInt();
	System.out.println( k+" "+m+" "+ans[m] );
    }
    return;
   }
}

  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3