행렬 추출 문제 V2 51nod-1084

이 문제는 한 번, 거꾸로 한 번 가면 수익이 가장 높고 한 자리에서 한 번만 받을 수 있도록 요구한다.
그러면 매트릭스에서 임계 위치를 제외하고 우리는 다양한 경로로 도달할 수 있기 때문에 수익이 가장 높고 모든 위치가 한 번만 도달할 수 있다. 그러면 바로 두 번 온다고 생각해도 무방하다. 그러나 우리는 두 번의 dp로 나눌 수 없다. 만약에 첫 번째가 가장 좋으면 두 번째도 가장 좋은 것을 찾는다. 합치면 가장 좋은 것이 아닐 수도 있기 때문에 우리는 동기화 처리를 해야 한다. 즉, 다중 dp이다.두 사람이 동시에 출발점에서 출발하고 두 사람의 경로가 겹치지 않도록 보증한다. 그러면 우리는 dp[steps][x][y]로 제steps - 1보를 표시할 때 첫 번째 사람이 x열에 있고 두 번째 사람이 y열에서 가장 큰 수익을 얻고 마지막에 출력dp[m + n][n][n]하면 된다. 왜냐하면 가장 뒤의 단계와 두 사람이 같은 열에 있을 때 반드시 같은 줄에 있기 때문이다.(칸이 하나밖에 남지 않았다)

#include 
#include 
#include
using namespace std;

typedef long long ll;

const int MAXN = 205;
const int MAX_STEPS = 405;

int res;
int m, n;
int A[MAXN][MAXN];
int dp[MAX_STEPS][MAXN][MAXN];

void input()
{
    scanf("%d%d", &m, &n);

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &A[i][j]);
        }
    }
}

void solve()
{
    for (int i = 2; i <= n + m; i++)
    {
        for (int j = 1; j <= n && i - j > 0; j++)//  i-j>0    i-j>=0；         ，      （   ）
        {
            for (int k = 1; k <= n && i - k > 0; k++)
            {
                if (j == k)
                {  //            
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][k - 1] + A[j][i -k]);
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - 1] + A[j][i - k]);
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][k] + A[j][i - k]);
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k] + A[j][i - k]);
                }
                else
                {   //     
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][k - 1] + A[j][i - j] + A[k][i - k]);
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - 1] + A[j][i - j] + A[k][i - k]);
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][k] + A[j][i - j] + A[k][i - k]);
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k] + A[j][i - j] + A[k][i - k]);
                }
                //printf("%d %d %d %d
",i,j,k,dp[i][j][k]);
            }
        }
    }
    cout << dp[n + m][n][n] << endl;
}

int main()
{
    input();
    solve();

    return 0;
}