Hướng dẫn giải của duong3982oj Contest 03 - Đường đi trên lưới
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giả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.
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.
Tác giả:
Subtask 1: ~N \le 3~
Vẽ tay, thử tất cả trường hợp.
Độ phức tạp: ~O~ (~N^2~) và rất nhiều giấy nháp.
Subtask 3: ~N \le 300~.
Chú ý: số lượt đi đường chéo không bao giờ vượt quá ~n~ lần. Xuyên suốt bài này, mình sẽ mặc định ~c = min(n, c)~
Gọi ~dp_{i, j, k}~ với ý nghĩa kết quả lớn nhất bạn thu được tại vị trí ~i, j~ trong bảng khi đã sử dụng ~k~ lượt đi chéo.
Ta có công thức quy hoạch động như sau:
- ~dp_{1, 1, 0} = a_{1, 1}~
- ~dp_{i, j, k} = max(dp_{i-1, j, k}, dp_{i, j-1, k}, dp_{i-1, j-1, k-1}) + a_{i, j}~
Đáp số: ~max(dp_{n, n, i})~ với mọi ~0 \le i \le c~
Độ phức tạp: ~O~ (~n^2 \times c~)
Code mẫu:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pp pair <int, int>
#define fi first
#define se second
#define yes cout << "YES\n"
#define no cout << "NO\n"
const int N = 1e3 + 9;
int n, c, a[N][N];
int dp[2][N][N];
signed main (){
ios_base::sync_with_stdio (false);
cin.tie (NULL);
cout.tie (NULL);
if (fopen ("input.txt", "r")){
freopen ("input.txt", "r", stdin);
freopen ("output.txt", "w", stdout);
}
cin >> n >> c;
if (c > n) c = n;
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> a[i][j];
int res = -1e18 - 9;
for (int i = 1; i <= n; i++){
for (int j = 0; j <= n; j++) for (int k = 0; k <= c; k++) dp[i & 1][j][k] = 0;
for (int j = 1; j <= n; j++) for (int k = 0; k <= c; k++){
dp[i & 1][j][k] = -1e18 - 9;
if (i == 1 && j == 1) dp[i & 1][j][k] = a[1][1];
if (i > 1) dp[i & 1][j][k] = max (dp[i & 1][j][k], dp[i & 1 ^ 1][j][k] + a[i][j]);
if (j > 1) dp[i & 1][j][k] = max (dp[i & 1][j][k], dp[i & 1][j - 1][k] + a[i][j]);
if (k && i > 1 && j > 1) dp[i & 1][j][k] = max (dp[i & 1][j][k], dp[i & 1 ^ 1][j - 1][k - 1] + a[i][j]);
}
}
for (int k = 0; k <= c; k++) res = max (res, dp[n & 1][n][k]);
cout << res;
}
Bình luận