제목 연결
이 문제는 루고 시련장의 2-17:T2제목의 대의.
n*m의 바둑판은 칸마다 0-100의 수치가 있다. 왼쪽 상단에서 출발하여 오른쪽과 아래로 내려가 오른쪽 하단에 도달할 수 있다. 오른쪽 아래에서 출발하여 왼쪽과 위로 올라가 왼쪽 상단에 도달할 수 있다. 2차례의 노선이 중복되지 않도록 하고 칸을 통과한 수치와 가능한 한 크도록 요구한다. 제목 분석
체면이 매우 직관적이어서 첫 번째 느낌은 깊이 검색하면 할 수 있고 50의 데이터만 있어서 아무렇게나 하면 AC를 폭력적으로 할 수 있을 것 같다. 본 문제는 DP 모듈이기 때문에 DP의 사고방식으로 분석한다. 사실 왼쪽 상단에서 오른쪽 하단으로 두 번 가다가 노선이 다르면 오른쪽과 아래 두 방향만 있기 때문에 상태의 추측이 많이 줄어든 것으로 볼 수 있다. 두 번 가야 하는데 이것은 바로 얽힌 문제이다. 노선이 중복될 수 없기 때문에 매번 두 칸을 걷는 것으로 이해할 수 있다. (x1, y1), (x2, y2). 아이디어 1: 4차원 DP
DP의 문제풀이 세트, 무엇을 설정하느냐고 묻는다: f[x1][y1][x2][y2]는 동시에 (x1, y1)와 (x2, y2)에 발을 들여놓는 것이 가장 좋은 것을 나타낸다. 전이 방정식은 다음과 같은 네 가지 상황을 고려해야 한다. 1) 모두 가로에서 온다.2) 모두 세로로 한다.3) 1 가로로 하고 2 세로로 한다.4) 1은 세로로, 2는 가로로 한다. 그래서: f[x1][y1][x2]=max(f[x1][y1-1][x2][y2-1], f[x1-1][y1][x2-1][y2], f[x1][y1-1][x2-1][y2][y2], f[x1-1][y1][y1][x2][y2][x2][x2][y2]]][y2-1])+a[y1][y2]; (x1, y1)와 (x2, y2)는 중첩할 수 없기 때문에 매거할 때 판단을 한다. 마지막 답은 f[n][m-1][n-1][m]일 것이다. 아이디어 1 참조 코드
//luogu1006： ： DP
#include
using namespace std;
int f[60][60][60][60];
int a[60][60];
int n,m;
int maxx(int x,int y,int j,int k)// 4
{
if(x
아이디어 2: 3D DP로 최적화
기본적인 사고방식과 4차원 DP의 변화는 없지만 간단한 관찰 분석을 할 수 있다. (x1, y1)과 (x2, y2)는 왼쪽 상단에서 출발하고 동시에 진행하기 때문에 같은 오른쪽 비스듬한 곳에 떨어진 것이 틀림없다.
그래서 다음과 같다. (x1+y1)은 (x2+y2)와 같다.
따라서 원래 4층의 순환은 3층으로 변할 수 있다. i는 현재 i사임을 나타내고 x1과 x2를 각각 매거하면 대응하는 좌표를 직접 계산할 수 있다. 이렇게 하면 데이터가 1000까지 증가하는 테스트 포인트에 적용할 수 있다. 아이디어 2 참조 코드:
//luogu1006： ： DP
#include
using namespace std;
int f[200][60][60];
int a[60][60];
int n,m;
int maxx(int x,int y,int j,int k)// 4
{
if(x
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
49일차 - 2022.04.20
Baekjoon에서 문제풀이
1) 문제 : 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제/ 첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.
첫째 줄부터 N번째 줄까지 차례대로 별...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
