[过河(过桥)问题] pku acm

Bridge over a rough river

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 910		Accepted: 319

Description

A group of N travelers (1 ≤ N ≤ 50) has approached an old and shabby bridge and wishes to cross the river as soon as possible. However, there can be no more than two persons on the bridge at a time. Besides it's necessary to light the way with a torch for safe crossing but the group has only one torch.

Each traveler needs t_i seconds to cross the river on the bridge; i=1, ... , N (t_i are integers from 1 to 100). If two travelers are crossing together their crossing time is the time of the slowest traveler.

The task is to determine minimal crossing time for the whole group.

Input

The input consists of two lines: the first line contains the value of N and the second one contains the values of t_i (separated by one or several spaces).

Output

The output contains one line with the result.

Sample Input

4
6 7 6 5

Sample Output

29

Source
, Western Subregion

题目的意思是说,几个人过桥(有的题目是用船过河),因为桥很窄,每次只能有两个人通过,因为看不清,还要用一火把照明(总共只有一个火把),两个人同时过桥的时候,花费的时间为两个人中速度最慢的那个人花费的时间.现给出N个人的单独过桥时需花费的时间,求出这N个人全部过桥要花费多长时间...

/*最佳方案构造：以下是构造N个人(N≥1)过桥最佳方案的方法：　　
1) 如果N=1、2，所有人直接过桥。　　
2) 如果N=3，由最快的人往返一次把其他两人送过河。　　
3) 如果N≥4，设A、B为走得最快和次快的旅行者，过桥所需时间分别为a、b；
 而Z、Y为走得最慢和次慢的旅行者，过桥所需时间分别为z、y。那么　　　　
 当2b＞a+y时，使用模式一将Z和Y移动过桥；　　　　
 当2b＜a+y时，使用模式二将Z和Y移动过桥；　　　　
 当2b＝a+y时，使用模式一将Z和Y移动过桥。
这样就使问题转变为N-2个旅行者的情形，从而递归解决之。
　    ……　　　　　　　　　
    A Z →　　　　　　　　　　
    A ←　　　　　　　　　　
    ……
也就是“由A护送到对岸，A返回”，称作“模式一”。

    ……　　　　　　　　　　
    ……　　
第n-2步：　　　A B →　　　
第n-1步：　　　　A ←　　　　
第n步：　　　  Y Z →　　
第n+1步：　　　　B ←　　　　　　　　　　
    ……
这个模式是“由A和B护送到对岸，A和B返回”，称作“模式二”。

*/
#include
#include
using namespace std;
int a[1001];
int main()
{
 int t,i,n,fast1,fast2,slow1,slow2,slow3,sum,l,r;
 cin>>t;
 while(t--)
 {
  sum=0;
  cin>>n;
  for(i=1;i<=n;i++)
   cin>>a[i];
  sort(a+1,a+n+1);
  fast1=a[1];fast2=a[2];slow1=a[n-1];slow2=a[n];slow3=0;
  l=1;r=n;
  while(n!=0)
  {
   if(n==1) {sum+=slow2;break;}
   if(n==2) {sum+=slow2;break;}
   if(n==3) {sum+=(slow2+slow1+fast1);break;}
   if(2*fast2>=fast1+slow1) {sum+=(slow1+slow2+2*fast1);r-=2;slow2=a[r];slow1=a[r-1];n-=2;}
   else {sum+=2*fast2+fast1+slow2;r-=2;slow2=a[r];slow1=a[r-1];n-=2;}
  }
  cout< }
 return 0;
}