UVA 10037 Bridge

過橋問題
必須將問題分

1. 一個人
2. 兩個人
3. 三個人
4. 四個人以上

(下文中的 A B C D 中都是 A最快D最慢的排序)
不論是一個人或是兩個人都可以直接走過去 ．
A B C三個人的話則可以
A C去 A回 A B去 或是
A B去 A回 A C去
依照題意uva好像兩種答案都可以接受？(時間一樣)

再來先看四個人 A B C D
因為D是最慢的 所以我們可以知道D的time是避不開的
那麼要讓D過去又能得到最快的解答
要不就是讓AD過去 A回來
或者是讓 CD 一起過去讓C的時間被D蓋過去
可是這時候因為必須讓C再回來 就沒有真的節省到C的時間
因此必須讓AB先過去A回來後再讓CD過去 然後讓B代替他們回來
因此就得出四個人中的唯一兩種解法
A D -> A -> AC -> A -> AB
或是
A B -> A -> CD -> B -> AB
我們會發現這兩種解法都是找出讓CD一起過去的最佳方案
所以就可以假設 當人數(n)大於等於四的時候
運用DP的概念 先讓最後兩個人過去 慢慢把n削減
如果n原本是奇數 那麼最後 n 會等於 3 再套三人的算法
如果n原本是偶數 那麼最後n會等於2 再套兩人的算法
如此一來就可以解決了

不過我覺得實在是很難理解或證明為什麼就是不斷讓最後兩個人過去可以形成最佳解
網路上對這題的討論蠻多的 但主要都是直接引用這個公眾解法
有另一個有趣的方法是使用F(n)去判斷一次過去一個人或過去兩個人
然後分別判斷F(n-1) & F(n-2)的狀態 有興趣可以參考下面這篇文
運用DP處理UVA10037

如果有人有很直觀的方法可以解釋如何想到以及理解這種解法的 歡迎不吝賜教

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <sstream>
using namespace std;
#define f1 (0)  //fastest 1
#define f2 (1)  // fastest 2
#define s1(n) n-1   //slowest 1
#define s2(n) n-2   // slowest 2

int main() {
    unsigned int TC, n, time[1000];
    cin >> TC;
    while(TC--){
        cin >> n;
        int people = n; //幾個人
        int total_time=0;
        vector steps;
        for(int i = 0; i < n; i++){
            cin >> time[i];
        }
        sort(time,time+n);
        //first count time
        while(n>3){ // multi-dudes
            //AB A CD B -> A+ 2B + D
            int t1 = time[f1] + 2*time[f2] + time[s1(n)];
            //AD A AC A -> 2A + C + D
            int t2 = 2*time[f1] + time[s2(n)] + time[s1(n)];
            if(t1 < t2){
                total_time += t1;
            }
            else{
                total_time += t2;
            }
            n = n-2;
        }
        if(n == 2){
            total_time += time[f2];
        }
        else if (n==3){
            total_time += time[f1] + time[f2] + time[s1(n)];
        }
        else if(n == 1){//one-man army
            total_time += time[f1];
        }
        cout << total_time <3){ // multi-dudes
            //AB A CD B -> A+ 2B + D
            int t1 = time[f1] + 2*time[f2] + time[s1(people)];
            //AD A AC A -> 2A + C + D
            int t2 = 2*time[f1] + time[s2(people)] + time[s1(people)];
            if(t1 < t2){
                printf("%d %d\n%d\n",time[f1],time[f2],time[f1]);// AB A
                printf("%d %d\n%d\n",time[s2(people)],time[s1(people)],time[f2]);//CD B
            }
            else{
                printf("%d %d\n%d\n",time[f1],time[s1(people)],time[f1]);//AD A
                printf("%d %d\n%d\n",time[f1],time[s2(people)],time[f1]);//AC A
            }
            people = people-2;
        }
        if(people == 2){
            // A B
            printf("%d %d\n",time[f1],time[f2]);
        }
        else if (people==3){
            // A B, A , A C
            printf("%d %d\n%d\n%d %d\n",time[f1],time[f2],time[f1],time[f1],time[s1(people)]);
        }
        else if (people == 1){
            printf("%d\n",time[f1]);
        }
        if(TC) cout << endl;
    
        
    }
    return 0;
}

參考概念Algorithmist