データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
42(1): 2021/10/10(日)19:42:09.58 ID:CKYp8hS8(1/2)調 AAS
>>41
ツリーを作って再帰にもできそうだけど、番号の1番大きい社員から少ない社員に向かって1つずつ処理していけば動的計画法になるね
最初に各社員に部下の給料のリスト（最初は空）を持たせて、社員番号Nから2番に向かって部下の給料のリストに値があればそこから自分の給与を計算して上司のリストに加えることを繰り返す
社員N番を含めて部下がいない、自分の番が回ってきても部下の給料リストが空なら1を上司のリストに加えればいい
60: 2021/10/26(火)11:33:36.58 ID:CwYCZWUI(2/2)調 AAS
このとき、長さ n のタスク列 S_1, S_2, …, S_{k_0-1}, R_{k_0}, R_{k_0+1}, …, R_{n} で
p(R_{k_0}) = p(T_{k_0})
p(R_{k_0+1}) = p(T_{k_0+1})
…
p(R_{n}) = p(T_{n})
を満たすようなものが存在することは明らかである。
このタスク列 S_1, S_2, …, S_{k_0-1}, R_{k_0}, R_{k_0+1}, …, R_{n} も貪欲法によって選ばれうるタスク列である。
ところが、タスク列 S_1, S_2, …, S_{k_0-1}, R_{k_0}, R_{k_0+1}, …, R_{n} は第k_0日において、 p(S_{k_0}) > p(T_{k_0}) = p(R_{k_0}) であるにもかかわらず、
タスク S_{k_0} を選択しないタスク列であるから、このタスク列は貪欲法によって選ばれうるタスク列ではない。
これは矛盾である。
よって、 S は空集合である。
85(1): 2022/09/26(月)20:52:32.58 ID:Sp/QOOjd(1)調 AAS
英語だけどイラスト付きで分かりやすく書いてある
https://medium.com/enjoy-algorithm/lower-bound-of-comparison-sorting-c3e2225e3419
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.014s