首页 > 专题系列 > Java解POJ > POJ 1351 Number of Locks [解题报告] Java
2013
11-09

POJ 1351 Number of Locks [解题报告] Java

Number of Locks

问题描述 :

In certain factory a kind of spring locks is manufactured. There are n slots (1 < n < 17, n is a natural number.) for each lock. The height of each slot may be any one of the 4 values in{1,2,3,4}( neglect unit ). Among the slots of a lock there are at least one pair of neighboring slots with their difference of height equal to 3 and also there are at least 3 different height values of the slots for a lock. If a batch of locks is manufactured by taking all over the 4 values for slot height and meet the two limitations above, find the number of the locks produced.

输入:

There is one given data n (number of slots) on every line. At the end of all the input data is -1, which means the end of input.

输出:

According to the input data, count the number of locks. Each output occupies one line. Its fore part is a repetition of the input data and then followed by a colon and a space. The last part of it is the number of the locks counted.

样例输入:

2
3
-1

样例输出:

2: 0
3: 8

解题代码:

/* @author:zeropinzuo */
import java.io.*;
import java.util.*;

public class Main{
 static Scanner cin;
 static long[] f,g;
	
 public static void main(String args[]){
  cin = new Scanner(System.in);
  f = new long[17];
  g = new long[17];
		
  g[1]=4;
  g[2]=14;
  for(int i=3;i< 17;i++)
	g[i]=3*g[i-1]+2*g[i-2];
		
  for(int i=2;i< 17;i++)
	f[i] = (1<< (2*i))-(1<< i)-g[i]+2;
			
  while(run()==true)
			;
 }
	
 static boolean run(){
   int n = cin.nextInt();
   if(n==-1)
	return false;
   if(n==16){
     System.out.println(16+": 3553389280");
     return true;
    }
			
   System.out.println(n+": "+f[n]);
   return true;
	
  }
}

  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)