Điểm tối đa 2 người thu thập được gặp nhau 1 lần trong ma trận C++

Cho ma trận điểm. 2 người từ 2 góc đối diện, đi đến góc còn lại (chỉ xuống/phải và lên/trái), được gặp nhau đúng 1 ô. Tối đa tổng điểm thu được (điểm ô gặp chỉ tính 1 lần).

Thuật toán (4 bảng DP)

• P1S: max điểm từ (0,0) đến (i,j).
• P1E: max điểm từ (i,j) đến (N-1,M-1).
• P2S: max điểm từ (N-1,0) đến (i,j).
• P2E: max điểm từ (i,j) đến (0,M-1).
• Thử mọi ô gặp (i,j) không ở biên: 2 cách chéo nhau → lấy max.

Ví dụ triển khai (C++)

#include <bits/stdc++.h>
#define M 3
#define N 3
using namespace std;

int findMaxPoints(int A[][M]) {
    int P1S[M+1][N+1]={0}, P1E[M+1][N+1]={0};
    int P2S[M+1][N+1]={0}, P2E[M+1][N+1]={0};
    for (int i=1; i<=N; i++)
        for (int j=1; j<=M; j++)
            P1S[i][j] = max(P1S[i-1][j], P1S[i][j-1]) + A[i-1][j-1];
    for (int i=N; i>=1; i--)
        for (int j=M; j>=1; j--)
            P1E[i][j] = max(P1E[i+1][j], P1E[i][j+1]) + A[i-1][j-1];
    for (int i=N; i>=1; i--)
        for (int j=1; j<=M; j++)
            P2S[i][j] = max(P2S[i+1][j], P2S[i][j-1]) + A[i-1][j-1];
    for (int i=1; i<=N; i++)
        for (int j=M; j>=1; j--)
            P2E[i][j] = max(P2E[i-1][j], P2E[i][j+1]) + A[i-1][j-1];
    int ans = 0;
    for (int i=2; i
Đầu ra
Max Points : 800