Rương kho báu (Zombie's Treasure Chest - UVa12325)
Bài toán yêu cầu chúng ta tối ưu hóa giá trị của rương có thể tích $N$ với hai loại vật phẩm có thể tích $S_1, S_2$ và giá trị $V_1, V_2$. Điểm khó khăn nằm ở việc các giá trị đầu vào có thể lên tới 32-bit, khiến phương pháp quy hoạch động thông thường bị quá tải bộ nhớ hoặc thời gian.
Chiến lược ở đây là sử dụng kỹ thuật duyệt thông minh dựa trên kích thước của các vật phẩm:
- Nếu $S_1$ lớn, số lượng vật phẩm loại 1 không thể quá nhiều ($N/S_1$). Chúng ta duyệt qua số lượng vật phẩm này.
- Nếu cả $S_1$ và $S_2$ đều nhỏ, chúng ta sử dụng nhận xét: $S_2$ vật phẩm loại 1 có cùng thể tích với $S_1$ vật phẩm loại 2. Ta chỉ cần chọn loại có giá trị trung bình cao hơn và chỉ duyệt số lượng vật phẩm của loại kia trong khoảng giới hạn nhỏ (dưới $S_1$ hoặc $S_2$).
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long i64;
void solve_treasure(int case_num) {
i64 n, s1, v1, s2, v2;
cin >> n >> s1 >> v1 >> s2 >> v2;
if (s1 * s1 > n) { // Duyệt s1 nếu s1 lớn
i64 best_val = 0;
for (i64 i = 0; i * s1 <= n; ++i) {
i64 current = i * v1 + (n - i * s1) / s2 * v2;
best_val = max(best_val, current);
}
cout << "Case #" << case_num << ": " << best_val << endl;
} else if (s2 * s2 > n) { // Duyệt s2 nếu s2 lớn
i64 best_val = 0;
for (i64 i = 0; i * s2 <= n; ++i) {
i64 current = i * v2 + (n - i * s2) / s1 * v1;
best_val = max(best_val, current);
}
cout << "Case #" << case_num << ": " << best_val << endl;
} else { // Cả hai đều nhỏ, tối ưu hóa dựa trên bội chung
if (v1 * s2 > v2 * s1) {
swap(s1, s2); swap(v1, v2);
}
i64 best_val = 0;
for (i64 i = 0; i <= s1; ++i) {
i64 current = i * v2 + (n - i * s2) / s1 * v1;
best_val = max(best_val, current);
}
cout << "Case #" << case_num << ": " << best_val << endl;
}
}
Trò chơi xoay vòng (The Rotation Game - UVa1343)
Đây là một bài toán tìm kiếm trạng thái mục tiêu với số bước di chuyển ít nhất. Giải thuật IDA* (Iterative Deepening A*) là lựa chọn tối ưu. Hàm heuristic $h(n)$ được xác định bằng số lượng chữ số khác với chữ số xuất hiện nhiều nhất trong 8 ô trung tâm. Vì mỗi bước di chuyển chỉ có thể đưa thêm tối đa một chữ số vào vùng trung tâm, nếu $depth + h(n) > max\_depth$, chúng ta có thể cắt tỉa nhánh đó.
Tính toán lũy thừa (Power Calculus - UVa1374)
Mục tiêu là tìm số phép nhân/chia ít nhất để đạt được $x^n$ từ $x^1$. Bài toán này tương đương với việc tìm chuỗi cộng/trừ ngắn nhất để có được số $n$.
Sử dụng IDA* với hàm cắt tỉa: Nếu giá trị lớn nhất hiện có nhân với $2^{max\_depth - current\_depth}$ vẫn nhỏ hơn $n$, thì không thể đạt được mục tiêu.
#include <cstdio>
#include <algorithm>
int sequence[100], target;
bool search(int step, int limit) {
int current_max = sequence[step];
if (current_max == target) return true;
if (step >= limit) return false;
// Cắt tỉa: sự tăng trưởng lũy thừa tối đa
int potential = current_max;
for (int i = step + 1; i <= limit; ++i) potential *= 2;
if (potential < target) return false;
for (int i = step; i >= 0; --i) {
// Thử phép cộng
sequence[step + 1] = sequence[step] + sequence[i];
if (search(step + 1, limit)) return true;
// Thử phép trừ
sequence[step + 1] = sequence[step] - sequence[i];
if (sequence[step + 1] > 0) {
if (search(step + 1, limit)) return true;
}
}
return false;
}
void solve_power() {
while (scanf("%d", &target) && target) {
for (int limit = 0; ; ++limit) {
sequence[0] = 1;
if (search(0, limit)) {
printf("%d\n", limit);
break;
}
}
}
}
Động vật lưới (Lattice Animals - UVa1602)
Bài toán yêu cầu đếm số lượng Polyomino cỡ $n$ khác nhau có thể nằm vừa trong khung hình chữ nhật $W \times H$. Điểm mấu chốt là việc định nghĩa tính "duy nhất" (không tính quay, lật, tịnh tiến).
Chúng ta có thể tạo ra tất cả các Polyomino bằng cách bắt đầu từ 1 ô và thêm dần các ô kề cạnh. Mỗi khi tạo ra một hình mới, ta chuẩn hóa nó (đưa về tọa độ tối thiểu (0,0)) và kiểm tra tất cả các biến thể quay/lật của nó trong một bảng băm hoặc tập hợp (set).
Phá hủy hình vuông (Square Destroyer - UVa1603)
Cho một lưới các que diêm, tìm số que tối thiểu cần loại bỏ để không còn hình vuông nào. Đây là bài toán phủ tập hợp (Set Cover) kinh điển. IDA* hoạt động tốt ở đây bằng cách luôn tìm hình vuông chưa bị phá hủy nhỏ nhất và thử loại bỏ từng que diêm cấu thành nên nó.
Xe cứu hỏa (Firetruck - UVa208)
Tìm tất cả các đường đi đơn từ đỉnh 1 đến đỉnh $k$ trong một đồ thị vô hướng. Mặc dù là bài toán DFS cơ bản, nhưng với 20 đỉnh, số lượng đường đi có thể rất lớn. Một bước tối ưu quan trọng là kiểm tra tính liên thông trước khi tìm kiếm: nếu từ đỉnh hiện tại không có cách nào tới được đích (sử dụng mảng đánh dấu từ kết quả BFS/DFS ngược từ đích), ta dừng tìm kiếm tại nhánh đó.
Hình đồ họa Golygons (Golygons - UVa225)
Yêu cầu tìm đường đi khép kín độ dài $1, 2, \dots, n$ trên lưới tọa độ, quay 90 độ sau mỗi bước và tránh chướng ngại vật. Do số bước giới hạn ở 20, ta dùng Backtracking. Một điều kiện cắt tỉa mạnh mẽ là khoảng cách Manhattan: nếu khoảng cách từ điểm hiện tại về gốc tọa độ lớn hơn tổng các bước đi còn lại ($\sum_{i=step+1}^{n} i$), ta có thể loại bỏ nhánh đó.
Cắt xích (Cutting Chains - UVa818)
Chúng ta cần mở một số mắt xích để nối tất cả thành một chuỗi duy nhất. Vì $n \le 15$, ta có thể duyệt tất cả $2^n$ trạng thái (mắt xích nào bị mở). Với mỗi trạng thái, kiểm tra xem các mắt xích còn lại có thỏa mãn:
- Không có mắt xích nào có bậc (degree) > 2.
- Không chứa chu trình (cycle).
- Số lượng thành phần liên thông sau khi trừ đi các mắt xích đã mở phải đủ nhỏ để các mắt xích mở có thể kết nối chúng lại thành một chuỗi.
Lập lịch đường ống (Pipeline Scheduling - UVa690)
Bài toán mô phỏng việc đưa các tiến trình vào một hệ thống pipeline mà không gây xung đột tài nguyên. Trạng thái xung đột được biểu diễn bằng bitmask. Khi một tiến trình mới bắt đầu tại thời điểm $t$, ta kiểm tra mask của nó với trạng thái hiện tại của pipeline bằng phép toán AND.
#include <iostream>
#include <vector>
using namespace std;
int N_cycles, min_total;
long long unit_usage[5];
vector<int> valid_offsets;
void find_schedule(int count, int current_time, vector<long long> state) {
if (current_time + (10 - count) * valid_offsets[0] >= min_total) return;
if (count == 10) {
min_total = current_time;
return;
}
for (int offset : valid_offsets) {
bool collision = false;
for (int i = 0; i < 5; ++i) {
if ((state[i] >> offset) & unit_usage[i]) {
collision = true;
break;
}
}
if (!collision) {
vector<long long> next_state(5);
for (int i = 0; i < 5; ++i)
next_state[i] = (state[i] >> offset) | unit_usage[i];
find_schedule(count + 1, current_time + offset, next_state);
}
}
}
Các hình vuông chồng lấp (Overlapping Squares - UVa12113)
Bài toán yêu cầu kiểm tra xem một cấu trúc lưới $4 \times 4$ có thể được tạo ra bằng cách xếp chồng tối đa 6 hình vuông cỡ $2 \times 2$ hay không. Có tổng cộng 9 vị trí có thể đặt hình vuông $2 \times 2$. Ta có thể sử dụng đệ quy để thử đặt các hình vuông theo mọi thứ tự và kiểm tra kết quả sau mỗi bước.