USACO - 3.1.3 - Humble Numbers

 

原创文章转载请注明出处

摘要：动态规划 ， 三星 

一. 题目翻译

1. 描述：

对于一给定的素数集合 S = {p1, p2, ..., pK},考虑一个正整数集合，该集合中任一元素的质因数全部属于S。这个正整数集合包括，p1、p1*p2、p1*p1、p1*p2*p3...(还有其它)。该集合被称为S集合的“丑数集合”。

        注意：我们不认为1 是一个丑数。

        你的工作是对于输入的集合S去寻找“丑数集合”中的第N个“丑数”。所有答案可以用longint(32位整数)存储。

补充：丑数集合中每个数从小到大排列，每个丑数都是素数集合中的数的乘积，第N个“丑数”就是在能由素数集合中的数相乘得来的（包括它本身）第n小的数。

2. 格式：

          INPUT FORMAT:

          第 1 行: 二个被空格分开的整数:K 和 N ， 1<= K<=100 ， 1<= N<=100,000.

          第 2 行: K 个被空格分开的整数:集合S的元素

          OUTPUT FORMAT:

          单独的一行，输出对于输入的S的第N个丑数。

3. SAMPLE：

          SAMPLE INPUT:

4 19

2 3 5 7

          SAMPLE OUTPUT:

27

          

二.  题解

1. 题意理解（将问题分析清楚，大致用什么思路）：

  很有意思的一道模拟题目，使用动态规划来实现。题目的思路是维护一个有K个数的池，池中的每一个数（c）都是由一个已经产生的丑数（a）与S中一个素数（b）的积，我们每次从池中选出一个最小的乘积（c）作为下个丑数。同时更新该乘积中丑数（a）为已产生丑数中的下一个（大于a的下一个丑数d）。

          这里给出一个示例，输入是sample中的输入，算法的处理过程请参考下图。等号左边是已产生的丑数集合，右边为上段文字所述的池。

 

2. 具体实现（具体实现过程中出现的问题）：

这道题目的动态规划方程与之前我们看到的动态规划方程有些小不同: F(n) = min{F(i1)*P(j1) , F(i2)*P(j2) ..... F(ik)*P(jk)}，F(n)表示产生的第n个丑数，P(n)表示是素数集合S中的第n个素数。

 

3. 需要注意的细节 ：

这里要特别注意可能出现重复的问题，如果出现重复的则计算下一个。

4. 启示:

          这道题目的动态规划方程比较特别，子问题的选择与移动不是简单的++，而是只有当特定的子问题满足备选条件时才继续像下移动。

          这种问题的解法注意积累与总结。

三.  代码

/*
ID:fightin1
LANG:JAVA
TASK:humble
*/

package session_3_1_3;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

public class humble {

	public static void main(String[] args) throws Exception {
		Scanner in = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		
		
//		Scanner in = new Scanner(new BufferedReader(new FileReader(
//		"humble.in")));
//		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
//		"humble.out")));
		
		int k = in.nextInt();
		int n = in.nextInt();
		long[] prims = new long[k]; //素数集合
		int[] index = new int[k]; //池中数字当前取到哪一个丑数
		ArrayList<Long> al = new ArrayList<Long>(); //产生的丑数集合
		HashSet<Long> hash = new HashSet<Long>(); //为了避免产生同样值得丑数
		
		for (int i=0;i<k;i++){
			prims[i] = in.nextInt();
			index[i] = 0;
		}
		al.add((long)1);
		while (al.size()<=n){
			long min = Long.MAX_VALUE;
			int minIndex = 0;
			for (int i=0;i<k;i++){
				long temp = prims[i]*al.get(index[i]);
				if (temp<min){
					min = prims[i]*al.get(index[i]);
					minIndex = i;
				} else if (temp == min){ //be attention , there may be some equal element
					index[i]++;
				}
			}
			al.add(min); //从池中选出乘积最小的数，加入池中
			index[minIndex]++;
		}
		
		pw.println(al.get(n));
		pw.close();
	}
}