3

好的,这是我必须做的

作为 MCI(猛犸蛋糕公司)的员工,您的工作是制作超大的分层生日蛋糕。分层生日蛋糕是通过将小的圆形蛋糕层并将它们堆叠在一起而制成的。

为了完成你的工作,你站在一条大传送带前,而不同大小的层从你面前经过。当你看到你喜欢的,你可以把它从传送带上拿下来,加到你的蛋糕上。

只要您遵循以下规则,您可以根据需要在蛋糕中添加任意数量的层:

一旦将一层添加到您的蛋糕上,它就无法移动。(它弄乱了糖衣。)因此,层只能添加到蛋糕的顶部。

每一层只在你面前经过一次。你可以接受也可以离开。如果你吃了,你必须把它加到蛋糕的顶部。如果你离开它,它会沿着传送带移动,永远不会回来。

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

您将被提前告知从传送带上下来的层的直径(以英寸为单位)。你的工作是使用这些层创建最高的蛋糕。例如,假设以下列表表示沿传送带向下的层的直径: 8 16 12 6 6 10 5

假设您将第一层(直径为 8 英寸)用于蛋糕。这意味着您可能不会采用第二层(因为您已经有一个 8 英寸大小的层,并且 16 英寸 > 8 英寸)。同样,你不能拿第三层,但你可以拿第四层(因为 6” < 8”)。

之后,你也可以取第五层(规则很简单,上面的层不能更大;它可以是相同的大小)。以这种方式进行,我们可以创建一个高度为 4 层的蛋糕: 8 6 6 5 但是,如果我们让第一层继续并从第二层开始,我们可以创建一个高度为 5 的蛋糕: 16 12 6 6 5

您的程序将处理多个输入集,每行一个。每行都以整数 N 开头,然后是 N 个正整数,表示蛋糕层的大小,按照它们到达传送带的顺序排列。N 永远是一个非负整数,0 N 100,000。每层的直径在 1 到 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();

    }

}
4

6 回答 6

2

正如我对几个答案的评论完全忽略了这一点,这是一个动态编程问题。

现在您添加了约束,很明显在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

阅读上面一行的方法很简单。我们以第一行为例:

0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1

这意味着我们可以制作的最高蛋糕的底数从 5 到 16 不等,它是由一个元素(我们的第一块,“5”)制成的。

然后我们得到'10',我们得到这条线:

0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 2 2

这意味着我们可以从 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] );
}
于 2010-12-12T21:55:12.413 回答
1

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

查看 Stack 数据结构,而不是 ArrayList。 一层推到堆栈上,然后使用peek对照传送带中的当前项目检查蛋糕堆栈最顶层的直径。

如果目标是找到可能最高的蛋糕,一种天真的方法是简单地应用上述算法,从传送带的第一层开始,一直到最后,并记录最终高度(stack.size())。然后重复以传送带中的第二个项目为基础,然后是第三个,依此类推,将结果高度与每个循环结束时记录的最大值进行比较。

于 2010-12-12T19:42:10.080 回答
1

这个输入序列很棘手:

10 45 25 40 38 20 10 32 25 18 30

一种只跳过引入层的简单方法会找到这些 [cakes]:

[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  
于 2010-12-12T21:19:57.043 回答
1

您要解决的问题是一个动态编程问题(尽管很简单)。

算法

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],max[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

然后我们找出列表 [1, 2, 2, 3, 4, 5, 4] 的最大值,即 5。

而且,如上所述,这是对他在问题描述中逐步介绍的示例的正确答案。


这个怎么运作

该算法通过保存每一层的最大值来工作。该问题解释说,对于任何给定的层,它只能堆叠小于或等于其直径的蛋糕。因此,任何给定层的最大值总是等于或小于皮带上的层的最大值加 1(计算层本身)。如果没有可以堆叠的层,我们知道该层的最大值为 1。

于 2010-12-12T21:43:24.580 回答
1

让我们来看看这个过程。每次我们在流水线上遇到一个层,我们都会做出一个决定:使用还是不使用这个层?总体上最好的结果是以下两个结果中的更好者:

  • 我们使用这一层,并在其上使用不大于该层的剩余层构建最高的蛋糕。

  • 我们不使用这一层,并使用任何剩余的层构建最高的蛋糕。

我们可以简单地用递归来建模——伪代码:

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.
于 2010-12-12T21:44:16.467 回答
0

其实很简单,是这样的:

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));
于 2010-12-13T01:50:04.403 回答