動態規劃問題

誰能幫我找到吃飯的最佳動態規劃算法this problem 動態規劃問題

在路上，在CCC的競爭對手正在排隊等候美味的炸薯條。 N（1≤N≤100）個競爭對手排隊進入自助餐廳。

運行CCC的醫生V在最後一刻意識到程序員只是討厭站在使用不同語言的程序員旁邊。謝天謝地，CCC只允許使用兩種語言：Gnold和Helpfile。此外，競爭對手已經決定，如果他們在一組至少K（1≤K≤6）的競爭對手中，他們將只進入自助餐廳。

V醫生決定迭代以下方案：

* He will find a group of K or more competitors who use the same language standing next to each other in line and send them to dinner. 
* The remaining competitors will close the gap, potentially putting similar-language competitors together.

所以V醫生記錄競爭對手的順序，方便。所有的競爭者都可以用餐嗎？如果是這樣，請發送給晚餐的競爭者組的最小數量是多少？輸入

第一行包含兩個整數N和K. 第二行包含的在線（H表示幫助文件，G表示Gnold）競爭者輸出

輸出序列的N個字符，在一個線，這個單數是晚餐形成的最小組數。如果不是所有程序員都可以用餐，則輸出-1。

來源

2011-03-04 GEP

如果你想得到一些答案，你應該適當地標記問題。 'trick'是一個非常無意義的標籤。 – 2011-03-04 13:39:32

是的，我試圖添加動態編程，但它拒絕它。 – GEP 2011-03-04 16:01:12

@kletoskletos - 這裏有使用動態編程的理由嗎？由於我們給出了Helpfile程序員的數量和Gnold程序員的數量，我們可以將他們的數字除以由Doctor V指定的組號碼。其餘的程序員需要被添加到已經組成的組中，噸超過六組。我想這就是動態編程發揮作用的地方。有趣的問題。 – 2011-03-04 17:10:57

我不希望以實際的方式爲您解決SPOJ問題，因此請將以下內容作爲多次DP的存在證明。

對於固定的K，可以用餐的字符串集合是無上下文的。我將使用g和h而不是G和H。例如，對於K = 3，一個語法看起來像

S -> ε | g S g S g S G | h S h S h S H 

G -> ε | g S G 

H -> ε | h S H

的想法是，要麼沒有用餐者，或具有至少K個第一小餐館進餐 - 1他人，任何兩個之間（以及其中的最後和最後）有一個可以用餐的字符串。

現在使用的CYK加權變體以找到最小權重語法分析，其中非空小號製作具有權重1，並且所有其他具有重量0對K固定，CYK的運行時間爲O（N 3 ）。

來源

2011-03-06 17:30:39 user635541

所以你說我可以使用一般版本的CYK算法在O（kN^3）時間內解決問題。 – GEP 2011-03-07 12:47:23

是的，在轉換成喬姆斯基範式之後，語法的大小呈線性。 – user635541 2011-03-07 12:57:11

問題是我不知道喬姆斯基的正常形式是什麼以及如何轉換它。事實上，這是我第一次看到這個CYK算法，但它看起來非常類似於矩陣鏈乘法算法。實際上，我正在考慮一種算法，它可以找到每種可能的剩餘食物的最優解，並將它們組合在一起。基礎是矩陣鏈乘法算法，每個卵巢需要額外的O（n^2）時間，總共需要O（n^5）。您能否以自下而上的方式更好地描述您的算法？ – GEP 2011-03-07 19:43:51

該子問題是讓每個人都能在特定狀態下用餐的最小羣體。有很多可能的行狀態，但只有少數可以看到，所以你的記憶應該可以用散列圖來完成。

這是一些僞代碼。

int dine(string line){ 
    if(hashmap.contains(line)){ 
     return hashmap.get(line); 
    } 
    if(line.length == 0){ 
     return 0; 
    } 
    best = N+1; 
    for(i=0;i<line.length;i=j){ 
     type = string[i]; 
     j = i+1; 
     while(type == string[j]){ 
      j++; 
     } 
     if(j-i >= K){ 
      result = dine(string.substring(0,i-1) + string.substring(j,string.length)); 
      if(result > 0 && result < best){ 
        best = result; 
      } 
     } 
    } 
    if(best == N+1){ 
     hashmap.insert(line, -1); 
     return -1; 
    } 
    else { 
     hashmap.insert(line, best+1); 
     return best+1; 
    } 
}

如果您已經找到該行的答案，請返回該答案。如果隊伍中沒有人，你已經完成了，你不需要再組隊。假設你不能組成任何組。然後嘗試通過嘗試所有連續組中相同想法的程序員來證明這個錯誤。如果這個羣體足夠大以便被選中，看看在刪除這個羣組後，需要多少更多的動作才能讓每個人進入餐廳。跟蹤所需的最少動作。

如果找不到刪除所有組的方法，則返回-1。否則，在移除一個組加上一個之後，返回所需的最少移動，以說明您在此步驟中進行的移動。

來源

2011-03-04 17:10:14

你可以給你的解決方案的複雜性和一些更多的解釋？ – GEP 2011-03-04 17:15:20

@dosdos對複雜性毫無頭緒。 – 2011-03-04 17:33:14

我相信你的解決方案可以及時得到指數。 – GEP 2011-03-04 18:19:13

分而治之？在中間附近的某個地方採取一個（可移動的）組，並且兩個組的任一側，比如...... HHHGGGGGHHHHH .... - 現在有兩種可能性。無論是那兩組H用餐在同一組中，或者他們不用。如果他們在同一組中吃飯，那麼他們之間的G必須作爲一組正好那些G（所以你不妨嘗試一下你的第一招）。如果他們不這樣做，那麼你可以分別解決左側和右側的子列表。無論是哪種情況，您都有一個較短的列表進行遞歸。

來源

2011-03-04 23:32:59

是的，但是這個算法的時間複雜度是多少？ – GEP 2011-03-05 00:20:26

我想或許一個更簡單的方法是，您要標記每次移除的第一個和最後一個元素。我相信它有潛力成爲指數型，但我不認爲有任何解決方法（你可以構造一些最壞的情況下的序列），但希望你的競爭對手輸入將是友好的:) – 2011-03-05 00:25:11

其實我正在開發一種算法像這樣的矩陣鏈乘法。 – GEP 2011-03-05 01:00:20

動態規劃問題

回答

相關問題