2011-2012 Waterloo Local Contest, 2 October, 2011 E : Class Schedule
解法
普通に状態を考えて普通に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; }