Hướng dẫn giải của Thẻ bài
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.
Hướng dẫn giải
Thẻ được bốc theo thứ tự từ 1 trở đi, mỗi thẻ hoặc bỏ vào ống tre tiếp theo (đúng màu: thẻ chẵn vào ống xanh, thẻ lẻ vào ống đỏ) hoặc không dùng. Điểm là ~10^6~ trừ đi số hiệu thẻ cuối cùng được dùng, nên cần cực tiểu hóa số hiệu thẻ cuối cùng.
Sub 1: Một hàng ~(k = 1)~ — ~O(n)~
Ống tre phải được lấp theo thứ tự, nên với mỗi ống lấy thẻ nhỏ nhất lớn hơn thẻ vừa dùng và đúng màu (cách thẻ vừa dùng 1 hoặc 2 đơn vị). Nếu chỉ nộp sub này: đúng 5/20 test (các test một hàng).
Sub 2: Hai hàng — quy hoạch động ~O(n \cdot m)~
Gọi ~f[i][j]~ là số hiệu thẻ cuối cùng nhỏ nhất khi hàng 1 đã đầy ~i~ ống và hàng 2 đã đầy ~j~ ống. Vì các thẻ được dùng theo thứ tự tăng dần nên thẻ kế tiếp là thẻ nhỏ nhất đúng màu lớn hơn ~f~: ta xét hai lựa chọn, thẻ đó vào ống tiếp theo của hàng 1 hoặc hàng 2, lấy giá trị nhỏ hơn. Giá trị ~f~ nhỏ hơn luôn tốt hơn nên chỉ cần lưu giá trị nhỏ nhất. Dùng mảng một chiều cuộn theo ~i~ để tiết kiệm bộ nhớ. Với độ dài ~\le 5000~ thì khoảng 25 triệu phép tính. Đáp án là ~10^6 - f[n][m]~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu (đọc/ghi file B4.INP/B4.OUT); nếu ~k = 1~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước. Kết quả: 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int k;
string s1, s2;
const int TOTAL = 1000000;
// thẻ nhỏ nhất lớn hơn L và đúng màu c (B: số chẵn, R: số lẻ)
int nxt(int L, char c) {
int par = (c == 'B') ? 0 : 1;
return ((L + 1) % 2 == par) ? L + 1 : L + 2;
}
// Sub 1: chỉ một hàng (k = 1): lần lượt với mỗi ống lấy thẻ gần nhất đúng màu — O(n)
void sub1() {
int L = 0;
for (char c : s1) L = nxt(L, c);
cout << TOTAL - L << "\n";
}
// Sub 2: quy hoạch động cho hai hàng — O(n * m)
// f[i][j] = số hiệu thẻ cuối cùng nhỏ nhất đã dùng khi hàng 1 đầy i ống, hàng 2 đầy j ống.
// Thẻ được bốc theo thứ tự tăng dần nên thẻ tiếp theo dùng cho ống tiếp của hàng nào cũng là
// thẻ nhỏ nhất đúng màu lớn hơn thẻ vừa dùng.
void sub2() {
int n = s1.size(), m = s2.size();
vector<int> f(m + 1, 0);
for (int j = 1; j <= m; j++) f[j] = nxt(f[j - 1], s2[j - 1]);
for (int i = 1; i <= n; i++) {
f[0] = nxt(f[0], s1[i - 1]);
for (int j = 1; j <= m; j++)
f[j] = min(nxt(f[j], s1[i - 1]), nxt(f[j - 1], s2[j - 1]));
}
cout << TOTAL - f[m] << "\n";
}
int main() {
freopen("B4.INP", "r", stdin);
freopen("B4.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> k >> s1;
if (k == 2) cin >> s2;
if (k == 1) sub1();
else sub2();
return 0;
}
Bình luận