NYOJ-712 보물찾기【dp】
보물을 찾다.
시간 제한:
1000ms | 메모리 제한:
65535 KB
난이도:
5
묘사
전설에 의하면 HMH대사막에 M*N 미로가 있는데 그 안에 많은 보물이 숨겨져 있다고 한다.어느 날 Dr. Kong은 미로의 지도를 찾았습니다. 그는 미로 안 곳곳에 보물이 있고 가장 소중한 보물은 오른쪽 아래에 숨겨져 있고 미로의 수출입은 왼쪽 상단에 있다는 것을 발견했습니다.물론 미로 속의 통로는 평탄하지 않고 곳곳이 함정이다.Dr. Kong은 그의 로봇 카드를 탐험하러 많이 가기로 결정했다.
그러나 로봇 카도가 왼쪽 상단에서 오른쪽 하단으로 내려갈 때는 아래로 내려가거나 오른쪽으로만 간다.오른쪽 아래에서 왼쪽 상단으로 돌아갈 때는 위로 올라가거나 왼쪽으로 갈 뿐 카도는 뒤돌아보지 않는다.(즉, 한 점을 최대 한 번 통과해야 함).물론 카도르도 길을 따라 있는 보물 하나하나를 가져갔다.Dr. Kong은 그의 로봇 카드가 가능한 한 많은 보물을 가지고 나오기를 바란다.Dr. Kong이 카드가 많으면 보물을 얼마나 많이 가져올지 계산하는 데 도움을 줄 수 있도록 프로그램을 작성해 주세요.
입력
첫 번째 줄: K는 몇 개의 테스트 데이터가 있는지 나타낸다.
다음은 각 그룹에 대한 테스트 데이터입니다.
1행: M N
2~M+1줄:Ai1 Ai2.......AiN(i=1,......m)
【제약조건】
2≤k≤5 1≤M, N≤50 0≤Aij≤100 (i=1,….,M; j=1,…,N)
모든 데이터는 정수다.데이터 사이에 공백이 하나 있다.
출력
각 그룹의 테스트 데이터에 대해 한 줄을 출력: 로봇 카드가 가장 많은 가치를 지닌 보물 수
샘플 입력
22 30 10 1010 10 803 30 3 92 8 55 7 100샘플 출력
120134#include<stdio.h>
#include<string.h>
#define Minn(a,b) a>b?b:a
int map[60][60];
int dp[140][60][60];
int Maxn(int a,int b,int c,int d)
{
int max=a;
if(max<b)
max=b;
if(max<c)
max=c;
if(max<d)
max=d;
return max;
}
int main()
{
int K;
int ans;
int m,n;
int i,j,k;
int y1,y2;
scanf("%d",&K);
while(K--)
{
scanf("%d%d",&m,&n);
for(i=m;i>=1;i--)
for(j=1;j<=n;j++)
scanf("%d",&map[i][j]);
memset(dp,0,sizeof(dp));
ans=0;
for(k=2;k<=n+m-1;k++)
{
for(i=Minn(k,n);i>1&&i>=k-m+1;i--)
{
y1=i+m-k;
for(j=i-1;j>=1&&j>=k-m+1;j--)
{
y2=j+m-k;
// printf("%d,%d %d,%d ",i,y1,j,y2);
dp[k][i][j]=Maxn(dp[k-1][i-1][j],dp[k-1][i-1][j-1],dp[k-1][i][j-1],dp[k-1][i][j])+map[y1][i]+map[y2][j];
if(ans<dp[k][i][j])
ans=dp[k][i][j];
}
}
}
/*printf("%d %d
",dp[2][2][1],dp[3][3][2]);
printf("%d %d %d %d
",dp[2][2][2],dp[2][2][1],dp[2][3][1],dp[2][3][2]);*/
ans=dp[n+m-2][n][n-1]+map[1][n];
printf("%d
",ans);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
