UVA-10037 Bridge 模拟+dfs - c++编程基础

题意：有n个人要过桥，而他们手中只有一个电筒，而过桥的人数最多不超过两个，过桥必须有电筒，每个人过桥的时间不一样，过桥的时间取决于最慢的人，问：让所有人都过桥所花费最小的时间。

分析：先没想到用dfs就可以做，还是分析问题不过全面，先分析是已经很明显的是：让一个花时间最小的人，:和后面人过桥，时间可能会很小，但是有另一种方法：先花时间少的两个人过去，再让最小的过来，再后面的人去两个，让最次小的过来，也可以行的通。以为自己没有找到正确的方法，想好久。看了别人的才知道这两种方法都有可能，用dfs搜依次就可以求出所有答案了。唉，dfs真让人摸不着头脑啊；

先排序：.

1.如果只有1个人，直接就过去，t=a1;

2.如果两个人，一起过去，t=a2；

3.如果三个人，让最小的和后面的人依次过去，t=a1+a2+a3;

4.(麻烦点).假设有a1,a2,a[x-1],a[x].这里的中间的就可以不管了。

方案1：t1=a2+a1+a[x]+a1+a[x-1] (让花时间最小的人和后面人依次过去,顺序无关)。

方案2: t2=a2+a1+a[x]+a2+a2(让最小的两个人先过去，然后最小过来，再让后面最大的两个过去，再让第二个小的过来)

方案选择：t1-t2=a1+a[x]-2*a2>0

先用递归求出时间，再递归打印路线就行了！

#include  
#include  
#include  
#include  
using namespace std ;  
  
int a[1005];  
  
int Get_time(int x)  
{  
    if(x==1) return a[0];  
    if(x==2) return a[1];  
    if(x==3) return a[0]+a[1]+a[2];  
    if(2*a[1]




3){  
        if(2*a[1]