POJ 3184 - Finicky Grazers

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

概要

数直線上の閉区間 [0, L] に牛が N 頭いる．

牛同士の間隔をできるだけ離そうとすると，距離はある整数 D か D+1 のいずれかになるはず．

牛を1メートル動かすのに1分かかる．

牛同士の間隔をできるだけ離すのに必要な最小の時間を答える．

制約

解法

ある距離 D は D = (L+1 - N)/N であり，余った距離 M = L+1 - N - (N-1)*D 個の D+1 の間隔ができる．

よって，M 個の D+1 の間隔をコストが最小になるように割り当てる問題となり，

dp[i][j] = i 頭目の牛までで j 個だけ D+1 の間隔を割り当てたときの最小コスト

で DP．

i 頭目の牛までで j 個 だけ D+1 の間隔を割り当てたとき，移動後の i 頭目の牛の位置 x は x = i + i*D + j だから，

dp[i+1][j] <- dp[i][j] + abs(x - (i 頭目の移動前の牛の位置))
dp[i+1][j+1] <- dp[i][j] + abs(x+1 - (i 頭目の移動前の牛の位置))

で更新していける．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N, L;
 8   scanf("%d %d", &N, &L);
 9   static int cows[10000];
10   for (int i = 0; i < N; i++) {
11     scanf("%d", &cows[i]);
12   }
13 
14   const int D = (L+1 - N)/N;
15   const int M = L+1 - N - (N-1)*D;
16   static int dp[10001];
17   static const int INF = 10000000;
18   fill_n(dp, M+1, INF);
19   dp[0] = cows[0];
20   for (int i = 1; i < N; i++) {
21     static int dp_next[10001];
22     fill_n(dp_next, M+1, INF);
23     for (int j = 0; j <= M; j++) {
24       const int x = i + i*D + j;
25       dp_next[j] = min(dp_next[j], dp[j] + abs(x - cows[i]));
26       if (j < M) {
27         dp_next[j+1] = min(dp_next[j+1], dp[j] + abs(x+1 - cows[i]));
28       }
29     }
30     copy(dp_next, dp_next+M+1, dp);
31   }
32   printf("%d\n", dp[M]);
33   return 0;
34 }
poj/3184.cc