2011-2012 Waterloo Local Contest, 2 October, 2011 E : Class Schedule

問題概要

C個の授業がそれぞれT箇所で開催されている。授業の疲労度と教室移動の疲労度が定義されているので、疲労度を最小化する問題。

解法

普通に状態を考えて普通にDPする。

acceptされたコード

計算量O(C*T^2)。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_C = 25;
const int MAX_T = 1000;
const int INF = 1<<29;

int C, T, L;
int ps[MAX_C][MAX_T], es[MAX_C][MAX_T];
int dp[MAX_C+1][MAX_T];

void init(){
	scanf("%d%d%d", &C, &T, &L);
	for(int i=0; i<C; i++){
		for(int j=0; j<T; j++){
			scanf("%d%d", ps[i]+j, es[i]+j);
		}
	}
}

int solve(){
	for(int i=0; i<=C; i++){
		fill(dp[i], dp[i]+T, INF);
	}

	for(int i=0; i<T; i++){
		dp[1][i] = ps[0][i] + es[0][i];
	}

	for(int i=1; i<C; i++){
		for(int j=0; j<T; j++){
			for(int k=0; k<T; k++){
				dp[i+1][k] = min(dp[i+1][k], dp[i][j] + es[i][k] + abs(ps[i][k] - ps[i-1][j]));
			}
		}
	}

	for(int i=0; i<T; i++){
		dp[C][i] += L - ps[C-1][i];
	}
	return *min_element(dp[C], dp[C] + T);
}

int main(){
	int T;
	scanf("%d", &T);
	for(;T--;){
		init();
		printf("%d\n", solve());
	}

	return 0;
}