需要帮助来了在Java

Question

OK这里蛋糕排序算法是我必须做的

由于MCI（猛犸蛋糕股份有限公司）的员工，这是你的工作，以创建非常大的 分层的生日蛋糕。分层的生日蛋糕是通过将小圆形蛋糕层和将它们堆叠在彼此之上而制成的。

为了完成你的工作，你站在一个大型传送带 的前面，而不同大小的层穿过你的面前。当你看到一个你喜欢的人时，你可以把它从 传送带上取下，并将它添加到你的蛋糕上。

您可以尽可能多的层添加到你的蛋糕，你想， 只要你遵循下列规则：

一旦一个图层添加到你的蛋糕就不能移动。 （它会搅起结冰。）因此，图层 只能添加到蛋糕的顶部。

每层仅在您面前经过一次。你可以拿走它或者离开它。如果你拿它，你 必须将它添加到你的蛋糕的顶部。如果离开它，它将沿传送带向下移动， 永远不会返回。

蛋糕中的每一层必须至少与下面的图层一样小。您不能将较大的图层放在较小的图层上。

您将被预先告知输送带下方各层的直径（以英寸为单位）。 你的工作是使用这些图层创建最高的蛋糕。 例如，假设以下列表代表传送带上传来的图层的直径：8 16 12 6 6 10 5

假设您为蛋糕拍了第一层（直径为8“）。这意味着你可能不需要第二层（因为你已经有一个大小为8“和16”> 8“的层）。同样，你不能 采取第三层，但你可以采取第四层（自6“< 8”）。

接下来，你可以将 也拿到第五层（规则是简单的说，顶层不能更大;它可以是相同的大小） 大小。以这种方式进行，我们可以创建一个高度为4层的蛋糕：但是，如果我们让第一层继续并从第二层开始，我们可以创建一个高度为012的蛋糕。 5：16 12 6 6 5

您的程序将处理多个输入集，每行一个。每行将以整数N， 开头，接着是N个正整数，表示蛋糕层的大小，其顺序是：到达传送带上的次数为 。 N将始终是一个非负整数，0 N 100,000。每层 将具有1和100,000之间的直径。一条线，其中N = 0标志着 输入结束

Sample Input 
7 8 16 12 6 6 10 5 
10 45 25 40 38 20 10 32 25 18 30 
10 10 9 8 7 6 5 4 3 2 1 
0 

Sample Output 
5 
6 
10 

问题：找到蛋糕的最高层

这是我到目前为止写：

import java.io.*; 
import java.util.*; 

public class cake 
{ 
    private static String line; 
    private static ArrayList storage = new ArrayList(); 
    private static Integer highestStack = 0; 

    public static void main(String [] args)throws IOException 
    { 
      FileReader fin = new FileReader("cake.in"); 
     BufferedReader infile = new BufferedReader(fin); 

     FileWriter fout = new FileWriter("cake.out"); 
     BufferedWriter outfile = new BufferedWriter(fout); 


     line = infile.readLine(); 
     do 
     { 

      String[] temp = line.split(" "); 
      String number; 


       for(int j = temp.length-1; j!=0; j--) 
       { 

        if(Integer.parseInt(temp[j]) <= Integer.parseInt(temp[j-1])) 
        { 
         highestStack++; 
        } 

       } 

       storage.add(highestStack); 
      // Collections.sort(storage); 



      line = infile.readLine(); 
     }while(!line.equals("0")); 


     infile.close(); 
     outfile.close(); 

    } 

} 

Answer 1

正如我评论了几个答案完全缺少了这一点，这是一个动态规划问题。

现在您添加了约束条件，很明显，在O（n^2）中运行的动态编程解决方案是顺其自然的，并且事实上N不会超过100 000，因此很容易解决使用DP（并可能很难解决使用非DP算法）。

在任何时刻，你都得问问自己“我最多可以做到'x'的最佳状态”。

这是它看起来像你第一个例子：

0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 (Best we can do using pieces: 5) 
0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 2 2 (Best we can do using pieces: 5 10) 
0 0 0 0 0 1 2 2 2 2 2 2 2 2 2 2 2 (Best we can do using pieces: 5 10 6) 
0 0 0 0 0 1 3 3 3 3 3 3 3 3 3 3 3 (Best we can do using pieces: 5 10 6 6) 
0 0 0 0 0 1 3 3 3 3 3 3 4 4 4 4 4 (Best we can do using pieces: 5 10 6 6 12) 
0 0 0 0 0 1 3 3 3 3 3 3 4 4 4 4 5 (Best we can do using pieces: 5 10 6 6 12 16) 
0 0 0 0 0 1 3 3 4 4 4 4 4 4 4 4[5] (Best we can do using pieces: 5 10 6 6 12 16 8) 

Tallest cake as a height of: 5 

阅读上面一行的方式很简单。让我们在第一行，例如：

这意味着最高的蛋糕，我们可以有一个基地5随地到16是由一个元素（我们的第一件，'5'）。

然后我们得到的片 '10'，并且我们得到的线：

这意味着最高蛋糕我们可以从5到9将有一个元素（我们的'5'），从10到16我们可以填充两块（5和10）。

而且你重复那样，如果你想要的话，可以多达100 000个元素。

在我的电脑上，完整的100 000个解决方案需要不到20秒的时间才能使用动态规划解决。

下面是解决您的问题和输出上述代码。我有意地添加了输出语句，以便您可以看到正在发生的事情（只会看到相对较小的数字，这实际上只是为了得到算法的结果）。

public static void main(String[] args) { 
    doIt(new int[] {8,16,12,6,6,10,5}); 
    doIt(new int[] {0, 45, 25, 40, 38, 20, 10, 32, 25, 18, 30}); 
    doIt(new int[] {10, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}); 
} 

public static void doIt(int[] r) { 
    final int[] a= new int[r.length]; 
    int max = Integer.MIN_VALUE; 
    for (int i = 0; i < a.length; i++) { 
     max = Math.max(max, a[i]); 
     a[(a.length-1)-i] = r[i]; 
    } 
    final int[] s = new int[max+1]; 
    for (int i = 0; i < a.length; i++) { 
     final int size = a[i]; 
     s[size]++; 
     for (int j = size+1; j < s.length; j++) { 
      s[j] = Math.max(s[j-1], s[j]); 
     } 
     for (int j = 0; j < s.length; j++) { 
      System.out.print(" " + ((s[j]) > 9 ? "" : " ") + s[j]); 
     } 
     System.out.print(" (Best we can do using pieces: "); 
     for (int k = 0; k <= i; k++) { 
      System.out.print(a[k] + " "); 
     } 
     System.out.println(")"); 
    } 
    System.out.println("Tallest cake as a height of: " + s[s.length-1]); 
} 

Answer 2

我我不确定你在问什么，所以我会给你一些一般的提示。

查看Stack数据结构，而不是ArrayList。 将推入堆栈，然后使用peek检查传送带中当前物品的最上层蛋糕堆的直径。

如果目标是找到最高可能的蛋糕，那么简单的做法是简单地应用上述算法，从传送带的第一层开始，继续到最后，并记录最终高度（）。大小（））。然后重复传送带中的第二个项目作为基准，然后重复第三个，依此类推，将每个回路结束时得到的高度与记录的最大值进行比较。

Answer 3

这个输入序列是棘手：

10 45 25 40 38 20 10 32 25 18 30 

一个简单的方法，只有跳过导入层会发现这些[蛋糕]：

[10] 45 25 40 38 20 10 32 25 18 30 
10 [45 25] 40 38 20 10 32 25 18 30 
10 45 [25] 40 38 20 10 32 25 18 30 
10 45 25 [40 38 20 10] 32 25 18 30 <-- naive tallest, 4 
10 45 25 40 [38 20 10] 32 25 18 30 
10 45 25 40 38 [20 10] 32 25 18 30 
10 45 25 40 38 20 [10] 32 25 18 30 
10 45 25 40 38 20 10 [32 25 18] 30 
10 45 25 40 38 20 10 32 [25 18] 30 
10 45 25 40 38 20 10 32 25 [18] 30 
10 45 25 40 38 20 10 32 25 18 [30] 

游戏规则，你可以跳过任何层，但不只是领先的，所以在这种情况下正确的最高蛋糕将是：

10 [45] 25 [40] [38] 20 10 [32] [25] [18] 30 

或者写出来，只有选定图层：

45 40 38 32 25 18 

Answer 4

你试图解决的问题是一个动态编程的问题（虽然它比较简单）。

算法

public static int findMaxHeight(int[] layers) { 
    int[] max = new int[layers.length]; 

    for(int i=layers.length - 1; i >= 0; i--) { 
    int localMax = 0; 
    for(int j=0; j < layers.length; j++) { 
     if(layers[j] < layers[i]) { 
     if(max[j] > localMax) { 
      localMax = max[j]; 
     } 
     } 
    } 

    max[i] = localMax + 1;  
    } 

    int height = 0; 

    for(int i=0; i < max.length; i++) { 
    if(max[i] > height) { 
     height = max[i]; 
    } 
    } 

    return height; 
} 

---

一步一步

通过的是如何工作的一个步骤，可以考虑：

8 16 12 6 6 10 5 

因为我们要以相反的顺序，

5 10 6 6 12 16 8 

用5开始，有从[]小于5倍的值：

5 10 6 6 12 16 8 
1 

从[5]，最大值[5] = 1，因此1 + 1

5 10 6 6 12 16 8 
1 2 

等。 ..

5 10 6 6 12 16 8 
1 2 2 3 4 5 4 

然后我们发现列表的MAX [1，2，2，3，4，5，4]，它是5

而且，正如上面所解释的，这是正确的答案以他提供的例子说明他在问题描述中的地位。

---

如何使用

该算法通过采取节约每一层的最大值。问题解释说，对于任何给定的层，它只能堆叠小于或等于其直径的蛋糕。因此，任何给定图层的最大值将始终是一个等于或小于其大小的图层的最大值，它在皮带上加1（计算图层本身）。如果没有可堆叠的图层，我们知道此图层的最大值为1.

Answer 5

让我们来看看这个过程。每当我们在装配线上遇到一个图层时，我们都会做出决定：是否使用此图层？最好的结果是整体下列两项成果的更好：

• 我们使用该层，并在其上构建利用剩余的层不超过该层更大的最高蛋糕。

• 我们不使用此图层，并使用其余图层的任意构建最高蛋糕。然而

  tallest(remaining_layers, base_size) = # set base_size = infinity the first time 
      max(
       first_layer + tallest(other_layers, size(first_layer)), 
       tallest(other_layers, base_size) 
      ) 
      where first_layer = first(remaining_layers), 
        other_layers = rest(remaining_layers) 
  

  ，这本身不会削减它，因为我们应该用动态规划：伪 -

我们可以简单地用递归建模。

这个想法是，我们递归调用tallest与other_layers两次。如果我们可以称之为一次并拥有我们需要的所有信息，这不是很好吗？

我们需要什么信息？那么，如果我们有最高的蛋糕使用其余的蛋糕层来制作任何基础大小，那么我们就会设置：我们只挑选最适合当前蛋糕层的蛋糕，然后看看它是否与最高蛋糕相比有所改进总体。但是这里有个窍门：即使它没有改进，我们仍然可以获得信息。这个想法是为每个尺寸列出最“有效”的（最小基数）蛋糕。因此

我们的过程如下：

Set up a list of cakes, with one cake in it that has zero layers. 
# There will be, at all times, one cake in the list of any given height. 
# Starting at zero instead of one makes the iteration neater. 
For each layer on the conveyor belt, working **backwards** from the last: 
    Find the tallest cake in the list that fits on this layer. 
    Construct the cake 'c' consisting of that cake on top of this layer. 
    If there is already a cake in the list of the same height as 'c': 
     If the other cake has a smaller base, throw 'c' away. # It didn't help. 
     Otherwise, remove the other cake from the list. # 'c' is better. 
    If we still have 'c', add it to the list. 
The tallest possible cake for the input is now the tallest one in the list. 

Answer 6

其实很简单，它是这样的：

int[] layers = new int[] {x1,x2,x3...xn};  
int[] count = new int[layers.length]; 

for(int i = 1; i < layers.length; i++) 
{    
     for(int j = i+1 ; j < layers.length; j++) 
     { 
     if (layers[j] >= layers[i]) count[i]++; 
     }  
} 

answer = Collections.max(Arrays.asList(count));