在漆黑的夜里，四位旅行者來(lái)到了一座狹窄而且沒(méi)有護(hù)欄的橋邊。如果不借助手電筒的話，大家是無(wú)論如何也不敢過(guò)橋去的。不幸的是，四個(gè)人一共只帶了一只手電筒，而橋窄得只夠讓兩個(gè)人同時(shí)過(guò)。如果各自單獨(dú)過(guò)橋的話，四人所需要的時(shí)間分別是1、2、5、8分鐘；而如果兩人同時(shí)過(guò)橋，所需要的時(shí)間就是走得比較慢的那個(gè)人單獨(dú)行動(dòng)時(shí)所需的時(shí)間。問(wèn)題是，如何設(shè)計(jì)一個(gè)方案，讓這四人盡快過(guò)橋。
過(guò)橋問(wèn)題詳細(xì)的描述與解決方案請(qǐng)閱讀《過(guò)橋問(wèn)題——經(jīng)典智力題推而廣之五》,共7個(gè)小節(jié)，作者講述的非常細(xì)致。
結(jié)論我給再敘述一下:
以下是構(gòu)造N個(gè)人(N >= 1)過(guò)橋最佳方案的方法：
1)如果N=1或者N=2，所有人直接過(guò)橋。
2)如果N=3,由最快的人往返一次把其他兩人送過(guò)河。
3)如果N>=4,設(shè)A，B為走的最快的和次快的旅行者，過(guò)橋所需時(shí)間分別為a,b；而Z,Y為走得最慢的和次慢的旅行者，過(guò)橋所需時(shí)間分別為z,y。那么
當(dāng)2b>a+y時(shí)，使用模式一將Z和Y移動(dòng)過(guò)橋
當(dāng)2b<a+y時(shí)，使用模式二將Z和Y移動(dòng)過(guò)橋
當(dāng)2b=a+y時(shí)，使用模式一或者模式二將Z和Y移動(dòng)過(guò)橋。
這樣問(wèn)題就變成了N-2個(gè)旅行者的情形，遞歸解決即可。
注：這里的模式1指的是A將Z送過(guò)橋，然后返回，再把Y送過(guò)橋，再返回；模式2指的是A和B先過(guò)橋，然后A返回，Y和Z過(guò)橋，然后B返回
1. pku 1700 Crossing River (pku 3404 Bridge over a rough river)
就是最樸素的過(guò)橋問(wèn)題，問(wèn)最少所需時(shí)間
2. pku 2573 Bridge
在1的基礎(chǔ)上加上過(guò)橋所需要的步驟
3. zju 1579 Bridge
這里要用long long 真惡
4. hit 2540 Only One Boat
這個(gè)題目是過(guò)橋問(wèn)題的變種,題目的意思就是有N隊(duì)夫妻,現(xiàn)在要過(guò)河，但是只有一條船，并且船每次只能載兩個(gè)人。要求每一個(gè)妻子不能在丈夫不在的情況下與其他男人在一起，無(wú)論是船上還是岸上都不可以。問(wèn)最少的次數(shù)使得所有人過(guò)河，并打印具體的步驟(spj)。
這個(gè)問(wèn)題最少次數(shù)其實(shí)是固定的，不難推出如果有n隊(duì)夫妻，那么全部過(guò)河的最少次數(shù)是5*n-3。（這個(gè)原因我請(qǐng)教了這個(gè)題目的作者，他的意思是最優(yōu)的策略一定是兩個(gè)人坐船去彼岸，一個(gè)人坐船回此岸。因此最少次數(shù)是一定的)。知道了最少次數(shù)如何去打印具體步驟了，其實(shí)我們從樣例中3隊(duì)夫妻的說(shuō)明中可以得到一些啟發(fā)，就是說(shuō)經(jīng)過(guò)若干步之后可以使得一對(duì)夫妻"Leave"。 例如3隊(duì)夫妻的時(shí)候，標(biāo)號(hào)為1，2為第一對(duì)夫妻（奇數(shù)為男，偶數(shù)為女，下同）,標(biāo)號(hào)為3，4為第二對(duì)夫妻，標(biāo)號(hào)為5，6為第三對(duì)夫妻。那么由2，4首先坐船來(lái)到彼岸，然后2回去，2和6再來(lái)到彼岸回去，然后6回去，讓1，3過(guò)來(lái)，然后1和2離開，3回頭，3和5再過(guò)去，3和4離開，5回頭，5和6過(guò)河并離開。 現(xiàn)在轉(zhuǎn)換到n個(gè)人的情形。如果n=1或者2，那么很容易就能找到方案了，因此下面的情況針對(duì)n>=3的情況，我們可以先讓2n和2n-2過(guò)河，然后2n回來(lái)。(注：這個(gè)時(shí)候所形成的局面是此岸有n-1對(duì)夫妻和一個(gè)丈夫，彼岸有一個(gè)該丈夫的妻子）。下面2n和2n-4過(guò)河，然后2n-4回來(lái)，2n-1和2n-3過(guò)河，2n和2n-1 離開，2n-3返回。（注：這個(gè)時(shí)候的局面是此案有n-2對(duì)夫妻和一個(gè)丈夫，彼岸有一個(gè)該丈夫的妻子）。可以看出這是一個(gè)遞歸的過(guò)程。下面實(shí)現(xiàn)就簡(jiǎn)單了。
5. zju 2288 Across the River
題目大意: n個(gè)男生和m個(gè)女生過(guò)河.只有一只船,船每次最多裝k人且滿足如下條件:
任何時(shí)候岸邊(包括此岸和彼岸)和船上要么沒(méi)女生.否則女生不比男生少，問(wèn)最少要渡幾次才能使得所有人渡河完畢。
這個(gè)題目如果沒(méi)有說(shuō)要求彼岸也滿足這個(gè)要求（即女生不比男生少，或者沒(méi)有女生），我們可以利用貪心算法解決。
可以總是先把男生給送到彼岸，然后剩下來(lái)的部分都是盡量在滿足條件的情況下把男生往船上放，然后每次把船從彼岸送回來(lái)的人最好是女生。這樣可以使得結(jié)果次數(shù)最少。
但是現(xiàn)在要求的是此案和彼岸都必須滿足條件，這樣的話我們就只能bfs搜了。數(shù)據(jù)量不算大
TopCoder SRM 146 DIV2 1000代碼：
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
class BridgeCrossing
{
public:
int minTime(vector <int> times)
{
sort(times.begin(),times.end());
return search(times);
}
int search(vector <int> times)
{
int n=times.size();
if(n==1)
return times[0];
else if(n==2)
return times[1];
else if(n==3)
return (times[0]+times[1]+times[2]);
else
{
vector<int>v(times.begin(),times.end()-2);
if(2*times[1] > times[0]+times[n-2])
{
return 2*times[0]+times[n-1]+times[n-2]+search(v);
}
else
{
return 2*times[1]+times[n-1]+times[0]+search(v);
}
}
}
};