Hướng dẫn giải của Tổng giá trị lớn nhất
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhậpTác giả: , , ,
Hiểu bài toán
Bài toán yêu cầu tìm cách thay thế các ký tự '?' trong một xâu chỉ chứa 'a', 'b', '?' sao cho tổng giá trị của tất cả các cặp ký tự kề nhau là lớn nhất. Giá trị của từng cặp được xác định như sau: 'aa' = 0, 'ab' = 1, 'bb' = 0, 'ba' = -1. Nói cách khác, ta muốn tối đa hóa số lượng cặp 'ab' và tối thiểu hóa số lượng cặp 'ba'.
Các cách tiếp cận
Cách Quy hoạch động
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int main() {
int n;
if (!(cin >> n)) return 0;
string s;
cin >> s;
// dp[i][0]: tổng giá trị lớn nhất đến vị trí i nếu s[i] = 'a'
// dp[i][1]: tổng giá trị lớn nhất đến vị trí i nếu s[i] = 'b'
vector<vector<long long>> dp(n, vector<long long>(2));
// Khởi tạo giá trị ban đầu
if (s[0] == 'a' || s[0] == '?') dp[0][0] = 0;
else dp[0][0] = -1e18; // Không thể chọn 'a'
if (s[0] == 'b' || s[0] == '?') dp[0][1] = 0;
else dp[0][1] = -1e18; // Không thể chọn 'b'
for (int i = 1; i < n; ++i) {
dp[i][0] = -1e18;
dp[i][1] = -1e18;
// Nếu chọn s[i] là 'a'
if (s[i] == 'a' || s[i] == '?') {
// Kế thừa từ s[i-1] là 'a': cặp 'aa' -> +0
if (dp[i-1][0] != -1e18) dp[i][0] = max(dp[i][0], dp[i-1][0]);
// Kế thừa từ s[i-1] là 'b': cặp 'ba' -> -1
if (dp[i-1][1] != -1e18) dp[i][0] = max(dp[i][0], dp[i-1][1] - 1);
}
// Nếu chọn s[i] là 'b'
if (s[i] == 'b' || s[i] == '?') {
// Kế thừa từ s[i-1] là 'a': cặp 'ab' -> +1
if (dp[i-1][0] != -1e18) dp[i][1] = max(dp[i][1], dp[i-1][0] + 1);
// Kế thừa từ s[i-1] là 'b': cặp 'bb' -> +0
if (dp[i-1][1] != -1e18) dp[i][1] = max(dp[i][1], dp[i-1][1]);
}
}
cout << max(dp[n-1][0], dp[n-1][1]) << endl;
return 0;
}
- Time Complexity: O(N)
- Space Complexity: O(N)
Cách tiếp cận này sử dụng quy hoạch động. Ta định nghĩa dp[i][0] là tổng giá trị lớn nhất của xâu con từ 0 đến i khi ký tự thứ i được chọn là 'a', tương tự cho dp[i][1] (ký tự là 'b'). Để tính dp[i], ta xem xét giá trị của cặp (s[i-1], s[i]) dựa trên các lựa chọn hợp lệ trước đó. Ví dụ, nếu ta chọn s[i] là 'a', ta có thể đến từ s[i-1] là 'a' (tăng 0) hoặc 'b' (tăng -1). Phương pháp này đảm bảo tìm được tổng lớn nhất.
Cách Nhận thức (Greedy)
#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
if (!(cin >> n)) return 0;
string s;
cin >> s;
// Logic: Ta muốn có nhiều cặp 'ab' (giá trị 1) và ít cặp 'ba' (giá trị -1).
// Xét các cặp giá trị:
// 'aa' = 0
// 'bb' = 0
// 'ab' = 1
// 'ba' = -1
//
// Ta nhận thấy:
// Nếu ta thay thế '?' thành 'a' hoặc 'b' sao cho xâu kết quả có dạng 'a...ab...b' (một khối a rồi một khối b),
// thì ta chỉ có một cặp 'ab' duy nhất (nếu có), và không có cặp 'ba'.
// Cụ thể: aaa...abb...b
// Các cặp: aa, aa, ..., ab, bb, bb...
// Tổng giá trị = 1.
//
// Nếu xâu có các ký tự xác định cản trở việc này (vd: có 'b' ở đầu và 'a' ở cuối),
// ta phải tạo ra các cặp 'ba'. Tuy nhiên, các cặp 'aa' và 'bb' không ảnh hưởng.
//
// Ta chỉ cần quan tâm đến ký tự đầu tiên và cuối cùng của xâu.
// - Nếu ký tự đầu là 'b', ta không thể tránh cặp 'ba' đầu tiên nếu sau đó có 'a'.
// - Nếu ký tự cuối là 'a', ta không thể tránh cặp 'ba' cuối cùng nếu trước đó có 'b'.
//
// Thực tế, bài toán này có một công thức tổng quát rất đơn giản:
// Tổng giá trị = (Số ký tự 'b') - (Số ký tự 'a')
// ??? Không, hãy thử lại.
// 'ab' = 1 -> a=1, b=1.
// 'ba' = -1 -> a=1, b=1.
// Khoan, hãy xem xét kỹ hơn.
//
// Xét dãy giá trị:
// Giả sử ta có xâu 'a' + ... + 'b'.
// Nếu ta thay thế '?' để tạo ra xâu 'aa...abb...b', ta nhận được 1 đơn vị.
// Nếu ta có 'b' ở đầu, vd 'b...a...b', ta có thể thay '?' để được 'b...a...b'.
// Nếu ta có 'a' ở cuối, vd '...a...a', ta có thể thay '?' để được '...a...a'.
//
// Có một quy luật quan trọng:
// Tổng giá trị = (Số lượng 'b' ở cuối) - (Số lượng 'a' ở đầu) ???
//
// Hãy xem xét kỹ hơn các giải pháp đã cho:
// cout << s[n-1] - s[0];
// Logic này dựa trên giả định rằng:
// Nếu bắt đầu bằng 'a' và kết thúc bằng 'b', tổng là 'b' - 'a' = 1.
// Nếu bắt đầu bằng 'a' và kết thúc bằng 'a', tổng là 'a' - 'a' = 0.
// Nếu bắt đầu bằng 'b' và kết thúc bằng 'b', tổng là 'b' - 'b' = 0.
// Nếu bắt đầu bằng 'b' và kết thúc bằng 'a', tổng là 'a' - 'b' = -1.
//
// Nhưng tại sao lại như vậy?
// Ta có thể coi tổng giá trị là tổng các hiệu:
// sum(s[i+1] - s[i]) tren toan bo i.
// Neu s[i]='a' -> 0, s[i]='b' -> 1.
// sum(s[i+1] - s[i]) = s[n-1] - s[0] (Day la hieu chinh xac).
//
// Do do, viec chon 'a' o dau va 'b' o cuoi luon cho ket qua lon nhat.
// Neu dau la 'a' va cuoi la 'b' -> 1.
// Neu dau la 'a' va cuoi la 'a' -> 0.
// Neu dau la 'b' va cuoi la 'b' -> 0.
// Neu dau la 'b' va cuoi la 'a' -> -1.
//
// Do do, chung ta chi can:
// 1. Neu ky tu dau la '?' -> chon 'a'.
// 2. Neu ky tu cuoi la '?' -> chon 'b'.
// 3. Tinh s[n-1] - s[0].
//
// Kiem tra voi vi du:
// Ex 2: a?a?bb -> a a b a b b (Ne chon theo logic tren: a...b)
// Ex 2: a?a?bb -> a a b b b b (Total: a-b-b-b-b-b)
// Cac cap: aa(0), ab(1), bb(0), bb(0), bb(0). Tong = 1.
//
// Vay logic la:
// s[n-1] - s[0] chinh la ket qua.
// Vi s[i] la ASCII, 'a' = 97, 'b' = 98.
// 'b' - 'a' = 1.
// 'a' - 'b' = -1.
// 'a' - 'a' = 0.
// 'b' - 'b' = 0.
//
// Code logic:
if (s[0] == '?') s[0] = 'a';
if (s[n-1] == '?') s[n-1] = 'b';
// Neu bat dau bang 'b' va ket thuc bang 'a' (co the xay ra neu input fixed), tong am.
// Nhung ta muon tong lon nhat.
// Neu dau la 'b' va cuoi la 'a', ta co the chon lai '?' o dau/cuoi de thay doi.
//
// Kiem tra lai:
// Neu dau la 'b' (fixed), cuoi la 'a' (fixed): Tong = 'a' - 'b' = -1.
// Neu dau la 'b' (fixed), cuoi la '?': Chon cuoi la 'b' -> Tong = 'b' - 'b' = 0.
// Neu dau la '?', cuoi la 'a' (fixed): Chon dau la 'a' -> Tong = 'a' - 'a' = 0.
// Neu dau la '?', cuoi la '?': Chon dau 'a', cuoi 'b' -> Tong = 1.
//
// Vay lenh:
// if (s[0] == '?') s[0] = 'a';
// if (s[n-1] == '?') s[n-1] = 'b';
// cout << s[n-1] - s[0];
// La dung va toi uu.
if (s[0] == '?') s[0] = 'a';
if (s[n-1] == '?') s[n-1] = 'b';
cout << s[n-1] - s[0];
return 0;
}
- Time Complexity: O(1)
- Space Complexity: O(1)
Đây là phương pháp tối ưu nhất. Ta nhận thấy tổng giá trị của xâu có thể được tính toán dựa trên ký tự đầu tiên và ký tự cuối cùng của xâu sau khi thay thế '?'. Cụ thể, tổng giá trị xấp xỉ bằng s[n-1] - s[0] (trong đó 'a'=0, 'b'=1 hoặc theo mã ASCII). Để tối ưu, ta nên chọn ký tự đầu tiên là 'a' và ký tự cuối cùng là 'b' nếu chúng là '?'. Nếu chúng là ký tự cố định, ta phải chấp nhận giá trị tương ứng. Logic này được chứng minh bằng việc nhận thấy rằng tổng hiệu của các cặp kề nhau là một tổng telescope (tổng biên).
Cách Lập kế hoạch (Implementation)
#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
string s;
cin >> s;
// Xử lý ký tự đầu
if (s[0] == '?') s[0] = 'a';
// Xử lý ký tự cuối
if (s[n-1] == '?') s[n-1] = 'b';
// In ra hiệu
cout << (int)s[n-1] - (int)s[0] << endl;
return 0;
}
- Time Complexity: O(1)
- Space Complexity: O(1)
Đây là phiên bản đơn giản化的 của phương pháp nhận thức. Logic chính là: tổng giá trị cuối cùng phụ thuộc hoàn toàn vào ký tự đầu tiên và ký tự cuối cùng của xâu. Bằng cách thay thế '?' ở đầu bằng 'a' và '?' ở cuối bằng 'b', ta đảm bảo giá trị 'b' - 'a' = 1 (hoặc 0 nếu các ký tự này bị giới hạn bởi input).
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N) | O(N) | Quy hoạch động |
| 2 | O(1) | O(1) | Nhận thức (Greedy) |
| 3 | O(1) | O(1) | Lập kế hoạch (Implementation) |
Bài học kinh nghiệm
- Tổng giá trị của xâu bằng hiệu của ký tự cuối và ký tự đầu (s[n-1] - s[0]) khi coi 'a'=0, 'b'=1.
- Việc thay thế '?' ở vị trí đầu và cuối (nếu có) là chìa khóa để tối ưu hóa tổng giá trị. Đầu nên là 'a', cuối nên là 'b'.
- Các ký tự '?' ở giữa không ảnh hưởng đến tổng giá trị cuối cùng, vì chúng ta có thể sắp xếp chúng thành các cặp 'aa', 'ab', 'bb' sao cho không tạo ra 'ba' (trừ các cặp bắt buộc ở ranh giới)
Lỗi thường gặp
- Quên kiểm tra điều kiện ranh giới (N=1): Nếu N=1, không có cặp nào, tổng là 0.
- Sử dụng các biến số lớn cần đúng kiểu dữ liệu (long long) cho các phương pháp quy hoạch động, mặc dù lời giải tối ưu chỉ cần int.
- Lầm tưởng rằng cần xử lý tất cả các ký tự '?' trong khi thực tế chỉ cần quan tâm đến 2 ký tự đầu và cuối.
Bình luận