쪽지 전송(DP)

쪽지 돌리기(一)

시간 제한:
2000ms | 메모리 제한:
65535 KB
난이도:
5

묘사
소연과 소헌은 좋은 친구이자 같은 반 친구이다. 그들은 함께 있으면 늘 끝낼 수 없는 화제가 있다.한 차례의 소양 확대 활동에서 반 학생들은 m행 n열의 행렬을 만들었고 소연과 소헌은 행렬 대각선의 양쪽에 배치되어 직접 이야기를 나눌 수 없었다.다행히도 그들은 쪽지를 보내서 의사소통을 할 수 있었다.쪽지는 많은 학우들을 거쳐 상대방에게 전해져야 한다. 소연은 행렬의 왼쪽 상단, 좌표(1,1), 소헌은 행렬의 오른쪽 하단, 좌표(m,n)에 앉는다.소연에서 소헌으로 전해지는 쪽지는 아래로 또는 오른쪽으로만 전달되고, 소연에서 전해지는 쪽지는 위로 또는 왼쪽으로만 전달된다.행사 진행 중 샤오옌은 샤오쉬안에게 쪽지 한 장을 전달하고 샤오쉬안이 그에게 답장을 주기를 바란다.반의 모든 학우들이 전달을 도와줄 수 있지만 한 번만 도와줄 수 있다. 즉, 만약에 이 사람이 소연이에게 쪽지를 건네줄 때 도와주면 소연이에게 건네줄 때 도와주지 않는다는 것이다.반대로 해도 마찬가지다.
또 하나 주의해야 할 것은 반 전체의 모든 학우들이 도와주고 싶은 호감도가 높고 낮다는 것이다. (주의: 소연과 소헌의 호의도는 정의가 없고 입력할 때 0으로 표시한다) 0-1000의 자연수로 표시할 수 있다. 숫자가 클수록 호의를 나타낸다.소연과 소헌은 가능한 한 호의도가 높은 학우를 찾아서 쪽지를 전달하는 것을 도와주기를 바란다. 즉, 왕복 두 가지 전달 경로를 찾아서 이 두 가지 경로에서 학우들의 호의도가 가장 크도록 한다.지금, 소연과 소헌이 이런 두 가지 경로를 찾을 수 있도록 도와주세요.

입력
첫 번째 행에 N(0각 그룹의 테스트 데이터 입력의 첫 줄은 빈칸으로 구분된 정수 m와 n이 2개로 반에 m행 n열(2<=m, n<=50)이 있음을 나타낸다.
다음 m행은 m*n의 행렬로 행렬에서 i행 j열의 정수는 i행 j열에 앉아 있는 학생들의 호의도를 나타낸다(1000보다 크지 않다).각 행의 정수 n을 공백으로 구분합니다.
출력
각 그룹의 테스트 데이터 출력은 모두 한 줄로 하나의 정수를 포함하여 두 길을 오가며 쪽지를 전달하는 학생들의 호의도와 최대치를 나타낸다.
샘플 입력

샘플 출력

아이디어:
DP.학교 시합 제목과 뜻이 비슷하다.다른 점은 이것이 교차하는 것을 허용하지 않기 때문에 교차하는 상황을 배제하고 여러 그룹의 데이터 입력은 dp를 초기화해야 한다. 그렇지 않으면 다음 그룹의 결과에 영향을 줄 수 있다.

AC:

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int dp[110][55][55];
int Map[55][55];

int main () {
        int t;
        scanf("%d", &t);
        while (t--) {
                int n, m, sum;
                scanf("%d%d", &n, &m);
                for (int i = 0; i < n; ++i)
                        for (int j = 0; j < m; ++j)
                                scanf("%d", &Map[i][j]);

                memset(dp, 0, sizeof(dp));
                sum = n + m - 2;

                for (int k = 0; k <= sum; ++k) {
                    for (int x1 = 0; x1 < n; ++x1) {
                        for (int x2 = 0; x2 < n; ++x2) {

                                    int ans = 0;
                                    int y1 = k - x1, y2 = k - x2;

                                    if ((x1 < n - 1 || y1 < m - 1) &&
                                        x1 == x2) continue;

                                    if (k > 0 && x1 > 0 && x2 > 0)
                                        ans = max(ans, dp[k - 1][x1 - 1][x2 - 1]);
                                    if (k > 0 && x1 > 0 && y2 > 0)
                                        ans = max(ans, dp[k - 1][x1 - 1][x2]);
                                    if (k > 0 && y1 > 0 && x2 > 0)
                                        ans = max(ans, dp[k - 1][x1][x2 - 1]);
                                    if (k > 0 && y1 > 0 && y2 > 0)
                                        ans = max(ans, dp[k - 1][x1][x2]);
                                    if (y1 < 0 || y2 < 0) continue;

                                    dp[k][x1][x2] = ans + Map[x1][y1] + Map[x2][y2];
                        }
                    }
                }

                printf("%d
", dp[sum][n - 1][n - 1]);
        }
        return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

【경쟁 프로 전형적인 90문】008의 해설(python)

의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

쪽지 전송(DP)

쪽지 돌리기(一)

좋은 웹페이지 즐겨찾기