しばらくの間、この TopCoder の問題を解決しようとしてきましたが、この問題に対する DP ベースの解決策を思いつくことができません (以下を参照)。私はまた、問題に対する他の誰かによる解決策（以下にも示されています）を見つけましたが、それを理解することさえできません。
ここで解決策を教えてくれる人はいますか? どのような考え方がこの解決策につながるのかわかりませんか? 頭の中で再帰関係を確立するにはどうすればよいですか? この問題にどのようにアプローチするか、またはその解決策を書いた人がどのように書いたかはまったくわかりません。
PS: TopCoder に問題の社説があることは知っていますが、これはまだリリースされていません。どうしてか分かりません。
ここに問題があります
フォックス・シエルにはやらなければならない宿題がたくさんあります。宿題は、いくつかの相互に独立したタスクで構成されています。タスクが異なれば、完了までにかかる時間も異なる場合があります。int[] workCost が与えられます。i ごとに、i 番目のタスクが完了するまでに workCost[i] 秒かかります。彼女はパーティーに参加して友達に会いたいので、できるだけ早くすべてのタスクを完了したいと考えています。
主な問題は、シエルを含むすべてのキツネが宿題をするのが本当に嫌いだということです. 各キツネは、タスクの 1 つだけを実行する意思があります。幸いなことに、22世紀のロボット猫であるドラえもんは、キツネシエルに分割ハンマーを与えました。これは、キツネを2匹のキツネに分割できる魔法のガジェットです。
int splitCost が与えられます。キツネにスプリットハンマーを使うのは一瞬です。キツネにハンマーが使われると、キツネは裂け始めます。splitCost 秒後、彼女は 2 匹のキツネに変わります。元のキツネと別のまったく新しいキツネです。キツネが分裂している間は、再びハンマーを使用することはできません。
タスクの作業を中断することはできません。キツネがタスクに取り組み始めたら、それを終了する必要があります。複数のキツネが同じタスクで協力することは許可されていません。キツネは、ハンマーを使用して分割されている間、タスクに取り組むことはできません。同じキツネを複数回分割することが可能です。タスクの 1 つを解決する前と後の両方で、キツネを分割することができます。
キツネがすべてのタスクを解決できる最小時間を計算して返します。
解決策は次のとおりです。
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: