这个DP解决方案是如何接近的?

我一直在尝试解决这个TopCoder问题,我现在无法想出基于DP的解决方案(如下所示) . 我还找到了其他人解决问题的解决方案(下面也给出了),但我甚至无法理解 .

有人可以帮我解决这个问题吗?我不明白哪种思路会导致这个解决方案?我如何在脑海中 Build 复发关系?我完全不知道如何解决这个问题,或者编写该解决方案的人如何编写它 .

PS:我知道TopCoder有问题的社论,但是这个还没有发布 . 我不知道为什么 .

这是problem

Fox Ciel有很多功课要做 . 作业包括一些相互独立的任务 . 不同的任务可能需要不同的时间来完成 . 你得到一个int [] workCost . 对于每个i,第i个任务需要workCost [i]秒才能完成 . 她想参加一个派对并与她的朋友见面,因此她希望尽快完成所有任务 . 主要问题是包括Ciel在内的所有狐狸都非常讨厌做作业 . 每只狐狸都愿意做其中一项任务 . 幸运的是,哆啦A梦,一个来自22世纪的机器人猫,给了Fox Ciel一把分裂锤子:一个魔法小工具可以将任何狐狸分成两只狐狸 . 你得到一个int 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:

回答(2)

3 years ago

DP问题通常需要您制定几个示例,而获得它的唯一方法就是练习 . 尝试解决DP中的一些标准问题类型,如最长增加子序列,背包,硬币更改,矩阵乘法,TSP等 . 尝试这些类型的变量 .

至于上述问题,很少有事情需要注意:

  • 你需要N狐来完成N个任务(1个狐狸只能完成1个任务) . 所以,如果你需要再创建了.766116_t . 而且,如果你有超过1个任务,你必须拆分第一只狐狸 .

  • 每只狐狸你可以做两件事

  • 拆分它然后计算所花费的最短时间

  • 不要拆分,而是执行当前任务并计算用少量狐狸执行剩余任务所需的时间 .

  • 请注意,如果您有超过1个Fox(或1个Fox有1个任务),您只能选择不拆分 .

这应该可以让您了解问题 . 我没有彻底分析问题,但递归似乎没有创建重叠调用,即如果我有3个任务和2个狐狸,我只会调用该状态一次而不是更多 . 因此,解决方案是常规的递归解决方案,而不是DP .

3 years ago

社论现在在TopCoder网站上 . 你可以看看那里!