Cho ma trận ô: # chặn, * điểm, . đường. Đi từ (0,0) đến (n-1,m-1) (chỉ xuống/phải), rồi quay về (chỉ lên/trái), thu thập tối đa điểm * (mỗi * chỉ lấy 1 lần).
Thuật toán (DP 2 người đi cùng lúc)
- Biến đổi: 2 người đi từ (0,0) đến (n-1,m-1) cùng lúc, không cùng ô (trừ đầu/cuối).
- Trạng thái:
dp[r1][c1][r2], c2 = r1+c1-r2. - Chuyển trạng thái 4 trường hợp (r1±1, c1±1) × (r2±1, c2±1).
- Cộng điểm: nếu ô có * thì +1 (trừ khi 2 người cùng ô).
Ví dụ triển khai (C++)
#include <bits/stdc++.h>
#define MAX 5
#define N 5
#define M 5
#define inf 100000
using namespace std;
int cost(char grid[][M], int r1, int c1, int r2, int c2) {
if (r1==r2 && c1==c2) return grid[r1][c1]=='*' ? 1 : 0;
int ans = 0;
if (grid[r1][c1]=='*') ans++;
if (grid[r2][c2]=='*') ans++;
return ans;
}
int solve(int n, int m, char grid[][M], int dp[MAX][MAX][MAX], int r1, int c1, int r2) {
int c2 = (r1+c1) - r2;
if (r1==n-1 && c1==m-1 && r2==n-1 && c2==m-1) return 0;
if (r1>=n || c1>=m || r2>=n || c2>=m) return -inf;
if (dp[r1][c1][r2] != -1) return dp[r1][c1][r2];
int ch1=-inf, ch2=-inf, ch3=-inf, ch4=-inf;
if (c1+1
Đầu ra
8