Hướng giải của Kinh nghiệm (Olympic 30/4 K10 & K11 - 2019)
Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
🔎 Mô tả bài toán:
Hai người chơi An và Bình xuất phát từ ô (1,1) trong ma trận n x m, chỉ được di chuyển sang phải hoặc xuống dưới, và đến ô \((n,m)\). Mỗi ô chứa một giá trị điểm kinh nghiệm (có thể âm). Mục tiêu là tối đa hóa tổng điểm kinh nghiệm hai người đạt được.
🚧 Ràng buộc:
- Hai người không được đi qua cùng một ô (trừ ô bắt đầu và kết thúc)
- Điểm tại mỗi ô có thể âm, cần xử lý bằng INT_MIN
🧮 Ý tưởng quy hoạch động:
Ta dùng quy hoạch động 3 chiều:
dp[x1][x2][y1] = tổng điểm lớn nhất khi:
An đang ở (x1, y1)
Bình đang ở (x2, y2)
(y2 được tính bằng bước đi chung)
📌 Tính toán y2:
Do số bước di chuyển của hai người luôn bằng nhau:
steps = x1 + y1 - 2
=> y2 = steps - (x2 - 1) + 1
⚖️ Chuyển trạng:
Xét \(4\) hướng có thể di chuyển từ trạng thái trước:
- dp[x1-1][x2-1][y1] // cả 2 đều đi xuống
- dp[x1-1][x2][y1] // An xuống, Bình sang
- dp[x1][x2-1][y1-1] // An sang, Bình xuống
- dp[x1][x2][y1-1] // cả 2 sang phải
✅ Cập nhật giá trị:
- Nếu An và Bình đứng khác ô: được cộng cả \(2\) điểm
- Nếu trùng ô (chỉ cho phép tại \((n, m)\)): chỉ cộng \(1\) lần
📊 Khởi tạo:
dp[1][2][2] = a[1][2] + a[2][1];
dp[2][1][1] = a[1][2] + a[2][1];
📈 Kết quả:
cout << dp[n][n][m];
⏱️ Độ phức tạp:
- Thời gian: \(O(n^2 \times m)\)
- Bộ nhớ: \(O(n^2 \times m)\)
#include <bits/stdc++.h>
using namespace std;
const int MAX = 205;
int n, m;
int a[MAX][MAX];
int dp[MAX][MAX][MAX];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
// Nhập ma trận điểm kinh nghiệm
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
cin >> a[i][j];
// Khởi tạo trạng thái xuất phát đặc biệt:
dp[1][2][2] = a[1][2] + a[2][1];
dp[2][1][1] = a[1][2] + a[2][1];
// Duyệt tất cả vị trí có thể của An (x1, y1) và Bình (x2, y2)
for (int x1 = 1; x1 <= n; ++x1) {
for (int x2 = 1; x2 <= n; ++x2) {
for (int y1 = 1; y1 <= m; ++y1) {
// Bỏ qua hai trạng thái đã khởi tạo tay ở trên
if ((x1 == 1 && x2 == 2 && y1 == 2) || (x1 == 2 && x2 == 1 && y1 == 1))
continue;
int steps = x1 + y1 - 2;
int y2 = steps - (x2 - 1) + 1;
// Nếu y2 nằm ngoài biên ma trận thì bỏ qua
if (y2 < 1 || y2 > m) continue;
// Nếu không phải ô kết thúc và An trùng ô với Bình → không hợp lệ
if ((x1 != n || y1 != m) && x1 == x2 && y1 == y2) {
dp[x1][x2][y1] = INT_MIN;
continue;
}
int best = INT_MIN;
// Xét 4 khả năng đến từ trạng thái trước
if (x1 > 1 && x2 > 1)
best = max(best, dp[x1 - 1][x2 - 1][y1]);
if (x1 > 1 && y2 > 1)
best = max(best, dp[x1 - 1][x2][y1]);
if (x2 > 1 && y1 > 1)
best = max(best, dp[x1][x2 - 1][y1 - 1]);
if (y1 > 1 && y2 > 1)
best = max(best, dp[x1][x2][y1 - 1]);
if (best == INT_MIN) {
dp[x1][x2][y1] = INT_MIN;
continue;
}
// Cộng điểm: nếu hai người khác ô → cộng cả hai
int gain = a[x1][y1];
if (x1 != x2 || y1 != y2)
gain += a[x2][y2];
dp[x1][x2][y1] = best + gain;
}
}
}
cout << dp[n][n][m] << '\n';
return 0;
}
Nhận xét
*\[None\][user:[user:[user:
t
List item
## ##
]1
*\[None\]**]]]