## Thuật toán
Nhận thấy rằng bài toán tương đương với, tìm hai đường đi không giao nhau từ $(1, 1)$ đến $(n, n)$ có tổng giá trị lớn nhất.
Để thuận tiện lưu trữ trạng thái quy hoạch động, ta ánh xạ các ô $(i, j)$ trên bảng ô vuông thành các số từ $1$ đến $n^2$.
```cpp
#define TOIDX(r, c) ((r - 1) * (n) + (c))
```
Gọi $\texttt{dp[i][j]}$ là giá trị lớn nhất thu được khi đường thứ nhất kết thúc tại $i$ và đường đi thứ hai kết thúc tại $j$.
Bằng cách xét các ô đến được $i, j$ ta sẽ tính được $\texttt{dp[i][j]}$:
$$\texttt{dp[i][j]} = \max_{\substack{i' \in reach(i) \\ j' \in reach(j) \\ i' \neq j'}} \texttt{dp[i'][j']} + A_i + A_j$$
trong đó $reach(i)$ là tập các ô đến được $i$.
Cuối cùng kết quả là $\texttt{dp}[(n - 1, n)][(n, n - 1)] + A_{n, n}$
**Độ phức tạp. $O(n^4)$**
## Cài đặt tham khảo
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct Cell {
int r, c;
Cell(int _r = 0, int _c = 0) : r(_r), c(_c) {
}
bool operator == (const Cell other) {
return (r == other.r && c == other.c);
}
};
const int MAXN = 55;
const int INF = 1e18 + 7;
int n, a[MAXN][MAXN];
vector<Cell> dist[2 * MAXN];
#define TOIDX(r, c) ((r - 1) * (n) + (c))
int dp[MAXN * MAXN][MAXN * MAXN];
void init() {
cin >> n;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
int mat_dist = i + j - 2;
if (mat_dist != 0)
dist[mat_dist].push_back({i, j});
cin >> a[i][j];
}
}
for (int i = 0; i < MAXN*MAXN;++i)
for (int j = 0; j < MAXN*MAXN; ++j)
dp[i][j] = -INF;
}
vector<Cell> neighbors(const Cell &cell) {
vector<Cell> res;
if (cell.r > 1) res.push_back({cell.r - 1, cell.c});
if (cell.c > 1) res.push_back({cell.r, cell.c - 1});
return res;
}
void solve() {
dp[1][1] = a[1][1];
for (int mat_dist = 1; mat_dist <= 2 * n - 1; ++mat_dist) {
for (auto &i : dist[mat_dist]) {
for (auto &j : dist[mat_dist]) {
if (i == j) continue;
//cout << i.r << " " << i.c << " " << j.r << " " << j.c << ": \n";
vector<Cell> nei = neighbors(i);
vector<Cell> nej = neighbors(j);
for (auto &c1 : nei) {
for (auto &c2 : nej) {
if (c1 == c2 && (c1.r != 1 || c1.c != 1)) continue;
dp[TOIDX(i.r, i.c)][TOIDX(j.r, j.c)] = max(dp[TOIDX(i.r, i.c)][TOIDX(j.r, j.c)], dp[TOIDX(c1.r, c1.c)][TOIDX(c2.r, c2.c)] + a[i.r][i.c] + a[j.r][j.c]);
}
}
//cout << dp[TOIDX(i.r, i.c)][TOIDX(j.r, j.c)] << '\n';
}
}
}
cout << dp[TOIDX(n - 1, n)][TOIDX(n, n - 1)] + a[n][n];
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
init();
solve();
return 0;
}
```
chithanhnguyen
Created at
1 likes