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

*/