這個DP解決方案如何接近？

自從現在我一直在試圖解決這個TopCoder問題，並且我無法想出針對此問題的基於DP的解決方案（如下所示）。我還找到了別人解決問題的一個解決方案（同樣在下面給出），但我甚至無法理解它。這個DP解決方案如何接近？

任何人都可以幫我解決這個問題嗎？我不明白哪種思路會導致這種解決方案？我如何着手在我的腦海中建立復發關係？我完全不知道如何解決這個問題，或者寫這個解決方案的人是如何寫這個問題的。 PS：我知道TopCoder有問題的社論，但是這個還沒有發佈。我不知道爲什麼。

這裏的problem

福克斯彩虹有很多功課要做。作業由一些相互獨立的任務組成。不同的任務可能需要不同的時間完成。你得到一個int [] workCost。對於每個我，第i個任務需要workCost [i]秒才能完成。她想參加派對並結識她的朋友，因此她想盡快完成所有任務。

主要問題是，包括Ciel在內的所有狐狸真的很討厭做功課。每隻狐狸只願意完成其中一項任務。幸運的是，哆啦A夢是一隻來自22世紀的機器人貓，它爲Fox Ciel提供了一個分體式的錘子：一種可以將任何狐狸分成兩隻狐狸的魔法小工具。

給你一個int splitCost。在狐狸身上使用分割錘是瞬時的。一旦狐狸使用錘子，狐狸就開始分裂。在splitCost秒後，她將變成兩隻狐狸 - 原始狐狸和另一隻全新的狐狸。當狐狸在分裂時，不允許再次使用錘子。

任務的工作不能被中斷：一旦狐狸開始工作一項任務，她必須完成它。這是不允許多個狐狸合作在同一個任務。一隻狐狸在使用錘子分割時無法完成任務。有可能多次分裂相同的狐狸。她可以在之前和之後分裂一隻狐狸，她解決了其中一項任務。

計算並返回狐狸能夠解決所有任務的最少時間。

這裏的solution：通常

1:  
2: const int maxN = 55; 
3: int dp[maxN][maxN*2]; 
4: int N; 
5: int splitC; 
6: vector<int> workC; 
7:  
8: int rec(int,int); 
9: int FoxAndDoraemon::minTime(vector <int> workCost, int splitCost) { 
10:  
11: sort(workCost.begin(), workCost.end()); 
12: N = workCost.size(); 
13: splitC = splitCost; 
14: workC = workCost; 
15:  memset(dp, -1, sizeof(dp)); 
16:  
17: return rec(N-1, 1); 
18: } 
19:  
20: int rec(int jobs, int fox) 
21: { 
22: if(jobs == -1) return 0; 
23:  
24: int& val = dp[jobs][fox]; 
25: if(val != -1) return val; 
26: val = 0; 
27:  
28: if((jobs+1) <= fox) val = max(workC[jobs] , rec(jobs-1, fox-1)); 
29: else 
30: { 
31:  //split fox 
32:  val = splitC + rec(jobs, fox + 1); 
33:   
34:  if(!(fox == 1 && jobs > 0)) 
35:  val = min(val, max(workC[jobs], rec(jobs-1, fox-1))); 
36: } 
37: return val; 
38: } 
39:

來源

2012-04-28 Programming Noob

DP問題需要你工作了幾個例子，並獲得良好的它是實踐的唯一途徑。嘗試解決一些標準問題類型的DP像最長增加的子序列，揹包，硬幣更改，矩陣乘法，TSP等嘗試這些類型的變量。

至於上述的問題，要注意以下幾點：

你要n個狐狸來完成N個任務（1個狐狸將工作只有1任務）。所以，如果你已經克隆N狐狸，你不需要再創建。而且，如果你有超過1個任務，你必須拆分第一隻狐狸。
對於每個狐狸，你可以做兩件事情
- 拆分，然後計算所採取的最小時間
- 不要分裂，但執行當前任務和計算花費少了一個完成剩餘任務的時間狐狸。
  - 請注意，如果您有1個以上的Fox（或1個Fox有1個任務），則只能選擇不分割。

這應該給你對這個問題的想法。我沒有徹底分析這個問題，但遞歸似乎並沒有產生重疊的調用，即如果我有3個任務和2個狐狸，我只會調用一次這個狀態，而不會再調用這個狀態。所以，解決方案是一個常規的遞歸解決方案，而不是DP。

來源

2012-04-28 10:20:13 deebee

「如果你有超過1個任務，你必須拆分第一隻狐狸。」不對。你可以讓單個狐狸依次完成它們。但是，這可能不是最理想的。 – 2015-01-05 01:28:22

社論現在在TopCoder網站上。您可以在那裏看看！

來源

2012-06-20 20:23:48 user1444426

這個DP解決方案如何接近？

回答

相關問題