[BZOJ2072][POI2004] MOS过桥

时间:2024-10-07 08:35:56

Description
  一个夜晚一些旅行者想要过桥. 他们只有一个火把. 火把的亮光最多允许两个旅行者同时过桥. 没有火把或者多于2个人则不能过桥.每个旅行者过桥都需要特定的时间, 两个旅行者同时过桥时时间应该算较慢的那个. 我们想知道所有旅行者最少要花费多少时间才能全部过桥? Example 假如有4个人. 他们分别需要花费6,7,10,15分钟过桥.下图演示了他们如何使用44分钟全部过桥的,但他们能做得更快么?

Input
第一行一个数n 表示旅行者的总数, 1 <= n <= 100,000. 接下来n 行表示所有旅行者的过桥时间,时间从小到大排列,每个数不超过1,000,000,000.

Output
输出一个数表示最少过桥时间.

Sample Input
4
6
7
10
15

Sample Output
42

题解(from 网络):

我们考虑利用时间最小的两个人倒运,把时间大的人依次送过去,有两种方式:

1.时间最小的人和时间最大的人过去,然后时间最小的人把火把拿回来;

2.时间最小和第二小的两个人过去,然后时间最小的人把火把拿回来;接着时间最大和第二大的两个人过去,时间第二小的人把火把拿回来;

为了保证最优,应该不外乎这两种形式,那么令f[i]表示当前没有过桥的人还剩i个时的最短时间 DP即可。

代码:

--------------------------------------------------------------------------------------------------

#include <cstdio>
#define MAXN 100005

int min(int a, int b) { return a < b ? a : b; }

int n, a[MAXN], f[MAXN];

int main()
{
  freopen("MOS.in", "r", stdin);
  freopen("MOS.out", "w", stdout);
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = n - 1; i >= 2; i--)
  {
    f[i] = f[i + 1] + a[1] + a[i + 1];
    if (i <= n - 2) f[i] = min(f[i], f[i + 2] + a[1] + a[2] * 2 + a[i + 2]);
  }
  printf("%d", n >= 3 ? f[2] + a[2] : a[n]);
  return 0;
}

--------------------------------------------------------------------------------------------------