TCO12 1B 500pt : FoxAndDoraemon

問題概要

仕事がN(<50)個あり、各仕事は処理に必要な時間が決まっている。狐が1匹いる。狐は最大1個しか仕事をしない。また、狐は時間Sだけかけて分裂することができる。分裂して新しく生まれた狐はまた仕事を処理することができる。全ての仕事を終えるまでの時間を最小化する問題。

解法

時間のかかるものから処理した方が良いのは明らか。また、処理してから分裂させるより分裂させてから処理した方がよいこともわかる。
なので、時間の大きい順にソートしてから、（いくつまで処理するか、未処理な狐が何匹いるか）を状態にしてdpすればよい。
基底を調べる順序を間違えてWA。この間違いは久しぶりだ…。

acceptされたコード

#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

const int MAX_N = 50;
const int INF = 1<<29;

int N, S;
int as[MAX_N];
bool visited[MAX_N + 1][MAX_N + 1];
int memo[MAX_N + 1][MAX_N + 1];

struct FoxAndDoraemon {

	int minTime(vector <int> workCost, int splitCost) {
		N = workCost.size();
		S = splitCost;
		for(int i=0; i<N; ++i){
			as[i] = workCost[i];
		}
		sort(as, as + N, greater<int>());
		return rec(1, 0);
	}

	int rec(int n, int r){
		if(r >= N){
			return 0;
		}
		if(n + r >= N){
			return as[r];
		}
		if(visited[n][r]){
			return memo[n][r];
		}
		visited[n][r] = true;

		int& ret = memo[n][r] = INF;

		for(int cp=1; cp<=n; ++cp){
			ret = min(ret, max(as[r], S + rec(2*cp, r+n-cp)));
		}

		return ret;
	}
};