POJ 2336 - Ferry Loading II

http://poj.org/problem?id=2336

概要

同時に n 個の車を載せて t 分で川を渡れるフェリーがある． 与えられたスケジュールに従って m 個の車がくるので，すべての車を向こう岸に運ぶのにかかる時間を最小化する問題． 最小になるように運んだときのフェリーの往復回数も答える．

制約

• 0 < n, t, m < 1440

解法

dp[i] = i 番目までの車を運んだときの最短時間

という DP．

 1 #include <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int C;
 8   scanf("%d", &C);
 9   while (C-- > 0) {
10     int N, T, M;
11     scanf("%d %d %d", &N, &T, &M);
12     vector<int> cars(M);
13     for (int i = 0; i < M; i++) {
14       scanf("%d", &cars[i]);
15     }
16 
17     vector<int> dp(M+1, 10000000);
18     dp[0] = 0;
19     vector<int> cnt(M+1);
20     cnt[0] = 0;
21     for (int i = 0; i <= M; i++) {
22       for (int j = 1; j <= N && i+j <= M; j++) {
23         const int t = max(dp[i], cars[i+j-1]) + 2*T;
24         if (t < dp[i+j]) {
25           dp[i+j] = t;
26           cnt[i+j] = cnt[i]+1;
27         }
28       }
29     }
30     printf("%d %d\n", dp[M] - T, cnt[M]);
31   }
32   return 0;
33 }