2010-06-20 Multiprocessor Scheduling (UVa Live Archive Europe - Southeastern - 2009/2010 Bucharest (Romania)) UVa Live Archive Online Judge http://acmicpc-live-archive.uva.es/nuevoportal/data/p4545.pdf 問題 メインプログラムが2つあり、メインプログラムはサブプログラムをN個順番に実行することにより動作する。各サブプログラムはプロセッサーPで実行され、D時間で終了する。2つのメインプログラムで同時に同じプロセッサーを使うサブプログラムを動かすことはできず、またサブプログラムの動作を途中で止めることは出来ない。 最適なタイミング・順序でサブプログラムを実行したときに2つのメインプログラムが完了するまでの最短時間を求めよ。 1<=N<=300 1<=P<=10 1<=D<=15000 解法 グリーディーにサブプログラムを実行していき、同じプロセッサーを使おうとした場合にどちらを先に実行するかでメモ化再帰をすればO(N^3)で解ける。