부뚜막
n*m의 칸, Baker Vai는 (1,1)에서 (n,m)로 다시 (1,1) 칸에 들어갈 때마다 칸의 숫자를 수집할 수 있습니다. (칸마다 한 번만 갈 수 있습니다. (1,1) 이 칸은 제외) 최종적으로 수집한 숫자의 합이 얼마나 되는지 물어보세요.
문제 해결 방법:
제목을 두 대상을 구하는 동시에 (1,1)에서 (n,m)로 출발하는 도중에 만날 수 없고 상태가 이동할 때 dp[step][x][y]로 전환할 수 있다. step는 현재 걸음수를 대표하고 x, y는 각각 두 사람이 현재 있는 줄을 대표한다(소재열은 직접 구할 수 있다).분명히 step=m+n-1은 오른쪽 하단에 이르렀을 때 제목은 아래로 내려가거나 왼쪽으로 갈 수밖에 없다는 것을 의미한다. 그래서 너는 빙글빙글 돌 수 없다는 뜻이다. 다시 말하면 너는 목표와 점점 가까워질 수 밖에 없다. 먼 길을 돌아서 돌아갈 수 없고 번거로움을 많이 줄일 수 있다. 가로로 앉은 후에 걸음수와 명확한 관계가 있다. 그리고 네가 이전에 어떤 위치를 선택하든 얻을 수 있다.놓칠 걱정 없어요. 큰 거랑.그 다음에 상태 방정식:ans=max(둘 다 아래로, 하나는 오른쪽, 하나는 아래로, 하나는 오른쪽, 모두 오른쪽) 주의, 기억화 검색. 만약에 예전에 여기까지 검색한 적이 있다면 바로 되돌아간다. 각 층은 마지막 ans를 계산하고 이 층의 두 사람의 수를 더한다. 만약에 두 개의 가로 좌표가 같으면 두 번째는 필요 없다.
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a[110][110],dp[220][110][110];
int n, m;
int dfs(int step,int r1,int r2)
{
if(step == n+m-1)
{
if(r1 == r2 && r1 == n && step-r1+1 == m)
return a[r1][step-r1+1 ];
else
return -1;
}
int ans = dp[step][r1][r2];
if(ans != -1)
return ans;
if(r1 < n && r2 < n)
ans = dfs(step+1,r1+1,r2+1);
if(r1 < n && step-r2+1 < m)
ans = max(ans,dfs(step+1,r1+1,r2));
if(r2 < n && step-r1+1 < m)
ans = max(ans,dfs(step+1,r1,r2+1));
if(step-r1+1 < m&&step-r2+1 < m)
ans = max(ans,dfs(step+1,r1,r2));
ans += a[r1][step-r1+1] + ((r1==r2)?0:a[r2][step-r2+1]);
dp[step][r1][r2] = ans;
return ans;
}
int main()
{
int T;
scanf("%d",&T);
for (int i = 1 ; i <= T ; i++)
{
scanf("%d%d",&n,&m);
for (int j = 1 ; j <= n ; j++)
for (int k = 1 ; k <= m ; k++)
scanf("%d",&a[j][k]);
memset(dp,-1,sizeof(dp));
printf("Case %d: %d
",i,dfs(1,1,1));
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
