Nhờ các bạn xem bài này giùm nên làm thế nào

LanSG9x:

Em nghĩ em hiểu sai ý anh tengiday rồi. Thêm ví dụ của bạn gunshot9x làm em cũng nghĩ ra phương pháp.
Em giả sử n > 1 cho dễ.

Mã:

1) Sort mảng giảm dần a[1] >= a[2] >= ... >= a[n-1] >= a[n]
2) Với i chạy từ 1 và mỗi bước tăng 2, nếu m là số người còn bên bờ sông A tại mỗi bước thì ta có các trường hợp sau:
   a) Nếu m=3 thì thời gian là a[n] + a[n-1] + a[n-2]
   b) Nếu m=2 thì thời gian là a[n-1]
   c) Nếu m>3 thì có 2 trường hợp:
      c_i)  Nếu a[n-1] và a[n] hộ tống a[i] và a[i+1] qua sông rồi a[n] và a[n-1] quay về,
         khi đó thời gian là: a[n] + 2*a[n-1] + a[i].
      c_ii) Nếu a[n] hộ tống a[i] và a[i+1] qua sông rồi a[n] quay về,
         khi đó thời gian là: 2*a[n] + a[i] + a[i+1].
      Ta chỉ cần chọn số nhỏ hơn của 2 trường hợp c_i và c_ii

Ý tưởng là lúc nào cũng phải để cặp có thời gian qua sông lớn nhất đi trước. Còn "người hộ tống" thì cần giữ 2 đầu. Tại sao nó đúng thì ý nghĩ cũng tương tự là kết hợp người chèo thuyền về và cách chọn cặp lớn tới nhỏ.
Em nói được là làm được. Đây là code. Khuya rồi, em code nhanh rồi ngủ, kiểu này mai chắc ngủ lớp Marx quá.
[ah]

Mã:

int river_crossing(int *a, int n) {
    if (n < 1)
        return 0;
    if (n < 2)
        return a[0];


    qsort(a, 0, n - 1); // sap xep tu lon toi nho


    int tg = 0, i;
    for (i = 0; i < n - 3; i += 2)
        tg += min(a[n - 1] + 2 * a[n - 2] + a[i], 2 * a[n - 1] + a[i] + a[i + 1]);
    return tg + (i < n - 2 ? a[n - 3] + a[n - 2] + a[n - 1] : a[n - 2]);
}

[/ah]
@rchato: Bạn đừng điêu và lươn lẹo nhé!!! Ở đây k phải ở ngoài đời mà bạn dùng kiểu nói làm ăn đó. Tôi không nói anh đi sai luật, tôi bảo anh vượt đèn đỏ. K ai khờ đâu; lòng Tư Mã Chiêu ai cũng hiểu. Như thế em biết công ty thế nào rồi đấy!

Nhấn để mở rộng...

tuan.huynh.87:

Bạn quan sát hay. Cách làm cũng đúng đó. Nhưng bài này muốn CM thì không dễ đâu nha. Mình đã đọc bài này đâu đó rồi. Mình ủng hộ quan điểm của bạn Sút Toàn Trật đấy. Bạn đừng cãi gì cho mệt. Mình quan sát rum mấy năm rồi, hôm nay thấy bạn nhiệt huyết nên mình kể bạn nghe cái này
Hồi đó có bạn hỏi 6-7 bài lập trình tính thời gian, chạy thử trên máy mới i7 của thầy bạn đó. Có bạn A bảo rằng mấy bài đó không dễ ăn đâu. Sau đó có bạn B khác làm được 2-3 bài. Bạn A lập tức đem chạy bài đó trên máy đời cũ Pentium 4. Thời gian không qua còn đem lên cho mọi người xem. Còn tô màu gạch đích, chụp màn hình nữa. Lúc sau admin chạy thử trên máy cũng tàng tàng là vừa qua thời gian (nói gì máy mới i7). Không có gì để nói, sau đó bạn A quay sang dạy chủ thớt "những bài này rất cơ bản". Mà toàn nói những thứ đúng là "rất cơ bản" ai cũng biết. Bị chủ thớt nạt. Cuối cùng bạn A im luôn, không xin lỗi, không cám ơn gì cả. Da mặt cỡ nào đây trời!!! Mà bạn B cũng quá hiền, im lặng.
Còn có bài khác, chủ thớt hỏi mấy câu. Có bạn trả lời được. Rồi tự nhiên có bạn khác vào làm bài đó. Mà hoàn toàn bỏ hết câu hỏi của chủ thớt chỉ giải theo ý mình, còn bảo sai đề. Giống bạn nói đó "con gà ghét nhau vì tiếng gáy".
Qua bài "phương trình bậc 2" thì bạn thấy rồi, cần gì phải tranh hơn thua. Không xin lỗi, không cám ơn gì người ta. Ngay khi viết code, nhận xét 2 vòng lặp 10^5, rồi nói đến test là thể hiện ra trình độ. Bởi vậy chỉ nói và hay bắt bẻ thôi.

Lập trình rất rộng. Cho dù biết lập trình mấy bài này cũng chưa hẳn lập trình web giỏi và ngược lại. Rum có những bạn rất giỏi, nhưng tài cần đức. Có tài mà không có đức, nó leo lên thì dân dưới này chết hết. Admin của rum hiền quá!

Nhấn để mở rộng...

LanSG9x:

Bạn có thể cho em xem cái bài chèo thuyền đó ở đâu k? Có cách CM luôn hả?

Nhấn để mở rộng...

http://page.mi.fu-berlin.de/rote/Papers/pdf/Crossing+the+bridge+at+night.pdf

In the case where there are an arbitrary number of people with arbitrary crossing times, and the capacity of the bridge remains equal to two people, the problem has been completely analyzed by graph-theoretic methods.

Nhấn để mở rộng...

https://en.wikipedia.org/wiki/Bridge_and_torch_problem

tuan.huynh.87:

Khẩu khí lớn quá!!! Nếu như bạn tengiday là người mình quen thật, thì 10 năm về trước chính bạn đó đã đưa tài liệu cho mình về bài này đó nha. From Wikipedia,

HTML:

https://en.wikipedia.org/wiki/Bridge_and_torch_problem

Bạn nói câu "chạy cho đúng trước" là hiểu trình độ rồi, còn non lắm nha. Mình chờ kết quả bạn xem cái đó đúng hay sai đó!!!

Nhấn để mở rộng...

tuan.huynh.87:

@gunshot9x: Mình chả hiểu bạn nói gì luôn đó. Bạn bỏ tính nói đại ngôn và nói một cách rõ ràng đi. Tài liệu nào? Google không có sao? Mấy cái này không học đàng hoàng, tay ngang vào mà phán bừa "xem có đúng không". Sau đó quay sang nói đọc không hiểu. Đó không phải ngành của bạn mà bạn mạnh miệng dữ ha. NẾU BẠN LÀ MÌNH THÌ BẠN NGHĨ GÌ, CẢM GIÁC GÌ KHI NGHE NGƯỜI NGOÀI NGÀNH NÓI KIỂU ĐÓ????

Nhấn để mở rộng...

LanSG9x:

tuan.huynh.87: Em đọc chưa hiểu được. Chắc sau này sẽ hiểu. Nó được đăng trên tạp chí khoa học luôn. Quá ghê!!! Mà nè, nếu vét cạn thì bài này em vét như thế nào vậy? Bạn chỉ em đi.

Nhấn để mở rộng...

tuan.huynh.87:

@lansg9x: Bạn gunshot9x cho ví dụ có thể tham khảo. Nhưng mà chi tiết như lưu trạng thái ra sao (cái quan trọng nhất) thì bạn đó bỏ rồi (điển hình mấy bài của bạn đó đều thế). Lưu nguyên mảng cũng được, nhưng mà mỗi lần phải chạy so sánh mảng. Bạn biết xử lý bit thì encode nguyên cái trạng thái thành 2^(n+1) trường hợp thì so sánh dễ hơn. Ví dụ như 4 người đều ở bờ A, thuyến ở bờ A thì ban đầu là 11111 (5 con số 1 với 4 số đầu tượng trưng cho 4 người đang ở bờ 1, số 1 ở cuối tượng trưng cho thuyền đang ở bờ 1). Tức có nghĩa rằng trạng thái (2^5 - 1) được đánh dấu lại xem như trạng thái ban đầu. Ai ở bờ bên kia thì bit đó là số 0. Duyệt như thế nào thì bạn dùng đệ quy quay lui như bạn gunshot9x nói đó.

Nhấn để mở rộng...

int *a, n, *f;
long long int min_time = LLONG_MAX;

void helper(int status, long long int cur_time) {
    if (!status) // all people on B side
        min_time = min(min_time, cur_time);
    else if (cur_time < min_time) {
        if (status & 1) {
            // Boat at A. 2 people cross the river.
            for (int i = 1; i <= n; i++)
                if ((status >> i) & 1) {
                    for (int j = i+1; j <= n; j++)
                        if ((status >> j) & 1) {
                            int change2 = (status ^ (1 << i)) ^ (1 << j);
                            if (f[change2]) {
                                f[change2] = 0;
                                helper(change2 ^ 1, cur_time + max(a[i-1], a[j-1]));
                                f[change2] = 1;
                            }
                        }
                }
        }
        else {
            // Boat at B. Only 1 person can cross.
            for (int i = 1; i <= n; i++)
                if (!((status >> i) & 1)) {
                    int change1 = status ^ (1 << i);
                    if (f[change1]) {
                        f[change1] = 0;
                        helper(change1 ^ 1, cur_time + a[i-1]);
                        f[change1] = 1;
                    }
                }
        }
    }
}

void river_crossing_brute_force2() {
    f = (int *)malloc(sizeof(int) * (1 << (n+1)));
    for (int i = 0; i < (1 << (n+1)); f[i++] = 1);
    f[(1 << (n+1)) - 1] = 0;

    helper((1 << (n+1)) - 1, 0);

    free(f);
}

int main() {
    n = 7;
    a = (int *)malloc(sizeof(int) * n);
    a[0] = 2;
    a[1] = 10;
    a[2] = 12;
    a[3] = 14;
    a[4] = 16;
    a[5] = 18;
    a[6] = 20;

    river_corssing_brute_force2();
    printf("%lld\n", min_time);
}