NOIP 过河问题 月黑风高的夜晚

(过河问题)
在一个月黑风高的夜晚,有一群人在河的右岸,想通过唯一的一根独木桥走到河的左岸.在伸手不见五指的黑夜里,过桥时必须借照灯光来照明,不幸的是,他们只有一盏灯.另外,独木桥上最多能承受两个人同时经过,否则将会坍塌.每个人单独过独木桥都需要一定的时间,不同的人要的时间可能不同.两个人一起过独木桥时,由于只有一盏灯,所以需要的时间是较慢的那个人单独过桥所花费的时间.现在输入 N(2<=N<1000)和这 N 个人单独过桥需要的时间,请计算总共最少需要多少时间,他们才能全部到达河左岸.
例如,有 3 个人甲 乙 丙,他们单独过桥的时间分别为 1 2 4,则总共最少需要的时间
为 7.具体方法是:甲 乙一起过桥到河的左岸,甲单独回到河的右岸将灯带回,然后甲,丙在
一起过桥到河的左岸,总时间为 2+1+4=7.

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<bitset>
#include<deque>
using namespace std;#define SIZE 100
#define INFINITY 1000000
#define LEFT 1
#define RIGHT 0
#define LEFT_TO_RIGHT 1
#define RIGHT_TO_LEFT 0
int n,time[SIZE],pos[SIZE];
int max(int a,int b)
{ if(a>b)return a;elsereturn b;
}
int min(int a,int b)
{ if(a>b)return b;elsereturn a;
}int go(int stage)
{
int i,j,num,tmp,ans;
if(stage == RIGHT_TO_LEFT){num = 0;ans = 0;for(i = 1;i <= n;i ++)if(pos[i] == RIGHT){num++;if(time[i] > ans)ans=time[i];}if(num<=2) return ans;ans = INFINITY;for(i = 1;i <= n-1; i ++)if(pos[i] == RIGHT)for(j = i+1;j <= n;j++)if(pos[j] == RIGHT){pos[i] = LEFT;pos[j] = LEFT;tmp=max(time[i],time[j])+go(LEFT_TO_RIGHT); //if(tmp < ans)ans = tmp;pos[i]=RIGHT;pos[j]=RIGHT;} //ifposjreturn ans;
} //ifrtol
if(stage == LEFT_TO_RIGHT){ans = INFINITY;for(i = 1;i <= n ;i++)if(pos[i]==LEFT){pos[i] = RIGHT;tmp = time[i]+go(RIGHT_TO_LEFT);//if(tmp < ans)ans = tmp;pos[i]=LEFT;}return ans;}//ifltor
return 0;
}
int gogo(int n){int ans;if(n==1){ans=time[1];};if(n==2){ans=max(time[1],time[2]);};if(n==3) {ans=time[1]+time[2]+time[3];};if (n>=4) ans=min(2*time[1]+time[n-1]+time[n],time[1]+2*time[2]+time[n])+gogo(n-2);return ans;}
int main()
{int i;scanf("%d",&n);for(i = 1;i <= n;i ++){scanf("%d",&time[i]);pos[i] = RIGHT;}printf("go ans:%d\n",go(RIGHT_TO_LEFT));sort(time+1,time+1+n);printf("gogo ans:%d\n",gogo(n));return 0;
}
/*
3
1 2 4
ans:7
4
1 2 4 7
ans:14
4
1 2 10 11
ans:18
4
860 396 45 891
ans:2124
*/