Multiprocessor Scheduling (UVa Live Archive Europe - Southeastern - 2009/2010 Bucharest (Romania))

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)で解ける。