Hiểu bài toán

Bạn có một lưới n x m chứa các ô. Mỗi ô có một giá trị:

• Giá trị dương: Vàng loại 1.
• Giá trị âm: Vàng loại 2 (trị giá là giá trị tuyệt đối).
• 0: Đất trống.

Bạn có một chiếc máy đào có thể hoạt động 2 lần. Mỗi lần hoạt động, bạn chọn:

1. Một hàng bất kỳ.
2. Một chế độ (Chế độ 1: khai thác vàng loại 1, Chế độ 2: khai thác vàng loại 2).

Khi máy hoạt động:

• Nếu chế độ phù hợp với loại vàng ở ô, bạn thu được giá trị của vàng đó.
• Nếu chế độ không phù hợp (ví dụ: dùng chế độ 1 để đào ô có vàng loại 2), số vàng ở ô đó bị phá hủy và bạn không nhận được gì.
• Các ô đất trống không ảnh hưưởng.

Mục tiêu: Tìm cách chọn 2 hàng (có thể là hàngsame) và 2 chế độ tương ứng để tối đa hóa tổng số vàng thu được.

Các cách tiếp cận

Cách Brute Force (Tìm kiếm đầy đủ)

// Pseudocode logic
long long max_gold = 0;
for (int i = 0; i < n; i++) {
    for (int mode1 = 1; mode1 <= 2; mode1++) {
        long long gain1 = calculate_gain(i, mode1);
        for (int j = 0; j < n; j++) {
            for (int mode2 = 1; mode2 <= 2; mode2++) {
                long long gain2 = calculate_gain(j, mode2);
                // Phải trừ đi giá trị bị mất nếu hai lần đào xung đột
                // (Nếu cùng hàng và chế độ khác nhau)
                max_gold = max(max_gold, gain1 + gain2 - penalty);
            }
        }
    }
}

• Time Complexity: O(n^2 * m)
• Space Complexity: O(1)

Giả sử ta thử tất cả các kết hợp. Với mỗi hàng i và chế độ 1, ta thử mọi hàng j và chế độ 2. Tuy nhiên, có một sự tương tác phức tạp: nếu chọn cùng một hàng cho cả hai lần đào với các chế độ khác nhau, ta sẽ bị mất giá trị của loại vàng không được chọn.

Nếu n và m nhỏ (< 100), cách này có thể chấp nhận được. Nhưng với n, m <= 1000, độ phức tạp O(n^2 * m) là quá lớn (khoảng 10^9 thao tác). Do đó, phương pháp này không khả thi cho dữ liệu lớn.

Cách Tối ưu hóa hàng (Precomputation)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<long long> row1(n, 0), row2(n, 0);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            long long val;
            cin >> val;
            if (val > 0) row1[i] += val;   // Tổng vàng loại 1
            if (val < 0) row2[i] -= val;   // Tổng vàng loại 2 (trị giá dương)
        }
    }

    vector<long long> best_row_val(n);
    for (int i = 0; i < n; i++) {
        // Chọn chế độ tốt nhất cho hàng này nếu chỉ đào 1 mình nó
        // Lưu ý: Nếu ta chọn 2 hàng khác nhau, ta có thể chọn 2 chế độ tùy ý.
        // Nếu ta chọn 2 lần cùng hàng, ta phải chọn 1 chế độ cho lần 1 và 1 chế độ cho lần 2.
        // Nhưng nếu chọn 2 hàng KHÁC NHAU, ta có thể chọn Mode 1 cho hàng A và Mode 2 cho hàng B.
        best_row_val[i] = max(row1[i], row2[i]);
    }

    // Tìm 2 hàng lớn nhất
    long long max1 = 0, max2 = 0;
    for (long long val : best_row_val) {
        if (val > max1) {
            max2 = max1;
            max1 = val;
        } else if (val > max2) {
            max2 = val;
        }
    }

    // Trường hợp đặc biệt: Cố gắng chọn cùng 1 hàng 2 lần?
    // Nếu chọn cùng hàng 2 lần, ta phải chọn 2 chế độ khác nhau (vì nếu cùng chế độ, không khác gì 1 lần).
    // Nếu chọn 2 chế độ khác nhau cho cùng hàng i:
    //   Gain = row1[i] + row2[i]
    // Nếu chọn 2 hàng khác nhau i, j:
    //   Gain = best_row_val[i] + best_row_val[j]

    long long ans = max1 + max2;
    for (int i = 0; i < n; i++) {
        ans = max(ans, row1[i] + row2[i]);
    }

    cout << ans << endl;
    return 0;
}

• Time Complexity: O(n * m)
• Space Complexity: O(n)

Đây là cách tiếp cận chính xác cho bài toán này.

1. Tính toán mỗi hàng: Với mỗi hàng i, ta tính:

   • S1[i]: Tổng các số dương (vàng loại 1).
   • S2[i]: Tổng các số âm (vàng loại 2, quy đổi về dương).

2. Phân tích các chiến lược:

   • Trường hợp 1: Chọn 2 hàng KHÁC NHAU. Khi chọn hai hàng khác nhau, ta hoàn toàn tự do chọn chế độ cho mỗi hàng.

     • Nếu chọn hàng i với chế độ 1, ta được S1[i].
     • Nếu chọn hàng i với chế độ 2, ta được S2[i]. Vì ta muốn tối đa hóa, với mỗi hàng, ta sẽ chọn chế độ cho nó là max(S1[i], S2[i]). Bài toán quy về tìm hai số lớn nhất trong mảng max(S1[i], S2[i]).

   • Trường hợp 2: Chọn CÙNG MỘT HÀNG 2 lần. Nếu chọn cùng hàng i twice, ta phải chọn hai chế độ khác nhau (nếu giống nhau, kết quả bằng 1 lần).

     • Chế độ 1 và Chế độ 2: Ta thu được S1[i] + S2[i]. Ta cần so sánh giá trị này với trường hợp 1.

3. Kết luận: Kết quả là giá trị lớn nhất giữa:

   • max(S1[i] + S2[i]) (cùng hàng).
   • max_1 + max_2 (hai hàng khác nhau, lấy max của mỗi hàng).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán tách biệt các hàng. Việc khai thác vàng trong một hàng không phụ thuộc trực tiếp vào các hàng khác, trừ việc chọn hàng.
• Khi chọn hai hàng khác nhau, ta có thể tối ưu hóa độc lập từng hàng (chọn chế độ 1 hoặc 2 cho hàng đó). Do đó, ta chỉ cần quan tâm đến giá trị lớn nhất mỗi hàng có thể mang lại.
• Trường hợp mấu chốt là khi ta quyết định 'dành cả 2 lần đào' cho cùng một hàng để khai thác cả hai loại vàng (tổng S1 + S2).

Lỗi thường gặp

• Quên rằng nếu chọn hai hàng khác nhau, ta có thể chọn hai chế độ khác nhau (ví dụ: hàng A dùng chế độ 1, hàng B dùng chế độ 2). Nhiều người lầm tưởng phải chọn 1 chế độ chung.
• Sai sót khi tính toán giá trị vàng loại 2 (giá trị âm) - cần lấy giá trị tuyệt đối (hoặc cộng trừ đúng dấu).
• Bỏ qua trường hợp chọn cùng một hàng twice, dẫn đến mất đi cơ hội khai thác cả hai loại vàng trong cùng một hàng.