需要幫助來了在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));