jzoj 2558. 【NOIP2011模拟9.9】过河问题

发布于 2019-03-30  864 次阅读


题目描述

在一个大晴天,Oliver与同学们一共N人出游,他们走到一条河的东岸边,想要过河到西岸。而东岸有一条小船。
  船太小了,一次只能乘坐两人。每个人都有一个渡河时间T,船划到对岸的时间等于船上渡河时间较长的人所用时间。
  现在已知N个人的渡河时间T,Oliver想要你告诉他,他们最少要花费多少时间,才能使所有人都过河。
  注意,只有船在东岸(西岸)时东岸(西岸)的人才能坐上船划到对岸。

输入

输入文件第一行为人数N,以下有N行,每行一个数。
第i+1行的数为第i个人的渡河时间。

输出

输出文件仅包含一个数,表示所有人都渡过河的最少渡河时间

思路

递推,f[i]=min(f[i1]+a[1]+a[i],f[i2]+a[1]+a[2]2+a[i])
而且不用排序。。。。。。。。。

pascal

var
  a,f:array[0..1000000] of int64;
  i,j,k,n,m,s,x,y:longint;
  mi:int64;
function min(x,y:int64):int64;
begin
  if x

c++

#include 
using namespace std;
long long a[1000000],f[1000000];
int i,j,k,n,m,s,x,y;
long long ans;
__attribute__((optimize("O2")))
int min(int x,int y)
{
    if (x>y) return y;
    else return x;
}
__attribute__((optimize("O2")))
int main()
{
    scanf("%d",&n);
    for (i=1;i<=n;i++)
        scanf("%d",&a[i]);
    f[1]=a[1];
    f[2]=a[2];
    for (i=3;i<=n;i++)
    {
         f[i]=min(f[i-1]+a[1]+a[i],f[i-2]+a[1]+a[2]*2+a[i]);
    }
    printf("%d\n",f[n]);
    return 0;
}
]]>