pku 1700 Crossing River

http://acm.pku.edu.cn/JudgeOnline/problem?id=1700

题意：此题与3404如出一辙，问所有人通过河流所使用的最短时间。

此题我使用递归实现的，耗时较3404多；

#include <cstdio>

#include <algorithm>

using namespace std;

int time[1001];

int people[1001];

int k = 0;

int Work(int number)

{

 if(number == 1)//当只有一个人时

  return time[1];

 if(number == 2)//当只有两个人时

  return time[2];

 if(number == 3)//当只有三个人时

  return time[3]+time[1]+time[2];

 if(2*time[2] < time[1] + time[number-1])

  return time[1]+2*time[2]+time[number]+Work(number-2);//使用模式二移动人员   

 else

  return 2*time[1]+time[number]+time[number-1]+Work(number-2);   //使用模式一移动人员

}

int main()

{

 int test;int i;int number;

 scanf("%d",&test);

 while(test --)

 {

  scanf("%d",&number);

  for(i = 1;i <= number;i ++)

   scanf("%d",&time[i]);

  sort(time+1,time+number);//对所有人员使用时间进行排序

  printf("%d/n",Work(number));

 }

 return 0 ;

}

/*

1
4
1 2 5 10
      

17

*/