c++ - 这个 DP 解决方案是如何处理的？

Question

一段时间以来，我一直在尝试解决这个 TopCoder 问题，但我无法针对这个问题提出基于 DP 的解决方案(如下所示)。我还找到了其他人针对该问题的解决方案(也在下面给出)，但我什至无法理解。

谁能帮我解决这个问题？我不明白什么思路会导致这个解决方案？我如何着手在我的脑海中建立递归关系？我完全不知道如何解决这个问题，或者编写该解决方案的人是如何编写的。

PS:我知道 TopCoder 有针对问题的社论，但这个还没有发布。我不知道为什么。

这是 problem

Fox Ciel has lots of homework to do. The homework consists of some mutually independent tasks. Different tasks may take different amounts of time to complete. You are given a int[] workCost. For each i, the i-th task takes workCost[i] seconds to complete. She would like to attend a party and meet her friends, thus she wants to finish all tasks as quickly as possible.

The main problem is that all foxes, including Ciel, really hate doing homework. Each fox is only willing to do one of the tasks. Luckily, Doraemon, a robotic cat from the 22nd century, gave Fox Ciel a split hammer: a magic gadget which can split any fox into two foxes.

You are given an int splitCost. Using the split hammer on a fox is instantaneous. Once a hammer is used on a fox, the fox starts to split. After splitCost seconds she will turn into two foxes -- the original fox and another completely new fox. While a fox is splitting, it is not allowed to use the hammer on her again.

The work on a task cannot be interrupted: once a fox starts working on a task, she must finish it. It is not allowed for multiple foxes to cooperate on the same task. A fox cannot work on a task while she is being split using the hammer. It is possible to split the same fox multiple times. It is possible to split a fox both before and after she solves one of the tasks.

Compute and return the smallest amount of time in which the foxes can solve all the tasks.

这是 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:    

Answer 1

DP 问题通常需要您解决几个示例，而要熟练掌握它的唯一方法就是练习。尝试解决 DP 中的一些标准问题类型，如最长递增子序列、背包、硬币变化、矩阵乘法、TSP 等。尝试这些类型的变体。

关于上面的问题，有几点需要注意:

• 您需要 N 只狐狸来完成 N 项任务(1 只狐狸只能完成一项任务)。所以，如果你已经克隆了 N 只狐狸，你就不需要再创建了。而且，如果您有多个任务，则必须拆分第一只狐狸。
• 你可以用每只狐狸做两件事
  • 拆分，然后计算最少花费的时间
  • 不拆分，但执行当前任务并计算少一只狐狸完成剩余任务所需的时间。
    • 请注意，如果您拥有超过 1 只 Fox(或 1 只 Fox 执行 1 项任务)，您只能选择不拆分。

这应该会让您对问题有所了解。我还没有彻底分析这个问题，但是递归似乎没有产生重叠调用，即如果我有 3 个任务和 2 个狐狸，我只调用该状态一次，不再调用。因此，解决方案是常规递归解决方案而不是 DP。