똑똑한kk[DP]

똑똑하다

시간 제한:
1000ms | 메모리 제한:
65535 KB
묘사
똑똑한 "KK"
아프리카의 한 나라 전시관의 디자인 영감은 전설적인 색채가 풍부한 사막에서 갑자기 기복하는 모래언덕에서 비롯되었고 자국의 끊임없는 변화와 현란하고 다채로운 자연 경치와 도시 풍경을 나타냈다.전시관은 다섯 부분으로 구성되어 있으며, 관내 영화관에서 이라는 와이드 스크린 단편영화를 방영하는 것은 건국 이래 국민들의 생활 수준과 도시 거주 환경의 놀라운 변화를 반영하였다.
'모래언덕'마술의 영감은 독특하고 웅장한 자연 경관인 전설적인 색채가 풍부한 험준한 모래언덕에서 비롯되었다.웅장한 구조, 순환 가능한 건축 자재는 대자연과 더욱 잘 어울린다.한 바퀴 돌면서 그것이 바로 모래언덕의 끊임없이 변화하는 형태에서 영감을 얻는 것을 발견했다.외형은 어느 각도에서 관찰하든지 모래언덕의 특징을 똑똑히 식별할 수 있을 정도로 생동감이 넘친다.
그것의'비탈면'은 높이가 20미터에 달하는데, 미풍이 불어오는데, 너는 모래의 흐름을 느꼈니?손으로 건드렸더니 마술 마술이었다.그 표면의 스테인리스강 패널은 변화무쌍한 색채를 나타내고 서로 다른 각도에서 관찰하여 서로 다른 색채와 광택을 나타내기 때문에 흐르는 모래언덕의 광감을 모방한다.
세 번째 전시장에 들어서면 커다란 스크린이 있는데 기묘한 필터를 통해 관중들이 마치 직접 드넓은 사막에 온 것 같다.더욱 기묘한 것은 작은 동물'KK'가 사막 지역(사각형)의 왼쪽 상단에서 오른쪽이나 아래쪽 방향을 따라 오른쪽 하단으로 달리고 있는 것이 보였다.KK는 너무 똑똑해서 달리는 과정에서 가능한 한 많은 벌레를 먹는 선로를 선택할 수 있다.
너는 그것이 얼마나 많은 벌레를 먹었는지 아니?
입력
첫 줄: N M (1≤ N M ≤ 20 0 ≤ Xij ≤500 (i=1,2 치)
) 사막이 N*M의 사각형 영역임을 나타냅니다.
다음은 N줄: 줄마다 M개의 정수가 있고, Xi1 Xi2...Xim은 각 위치의 벌레 수를 표시한다(한 칸으로 칸막이)
KK는 오른쪽이나 아래로만 갈 수 있다고 가정하십시오.
출력
출력에는'KK'가 가장 많이 먹은 벌레의 수를 나타내는 정수가 있다.
샘플 입력

3 4
3 1 2 8
5 3 4 6
1 0 2 3

샘플 출력

24

/* 문제 풀이:
처음에 DFS로 만들었는데 아무리 고쳐도 시간 초과였는데 나중에 인터넷에서 찾아보니 의외로 가장 기초적인 dp문제라는 것을 깨달았다
*/
AC 코드:

#include<cstdio>
#include<cstring>
int max(int a,int b)
{
	 return a>b ? a:b;
}
int main()
{
	int n,m,i,j,a[22][22];
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		memset(a,0,sizeof(a));
		for(i=1; i<=n; i++)
		{
			for(j=1; j<=m; j++)
			{
				scanf("%d",&a[i][j]);
			}
		}
		for(i=1; i<=n; i++)
		{
			for(j=1; j<=m; j++)
			{
				a[i][j]=a[i][j]+max(a[i-1][j],a[i][j-1]);
			}
		}
		printf("%d
",a[n][m]);
	}
}

DFS 시간 초과:

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m,s,ans;
int a[22][22],dir[2][2]={{0,1},{1,0}},vis[22][22];
void dfs(int x,int y)
{	
	if(x==n-1&&y==m-1)
	{
		ans=max(ans,s);
		return;
	}
	if(x<0||y<0||x>=n||y>=m) return;
	for(int i=0; i<2; i++)
	{
		int xx=x+dir[i][0];
		int yy=y+dir[i][1];
		if(xx>=0&&yy>=0&&xx<n&&yy<m&&!vis[xx][yy])
		{
			vis[xx][yy]=1;
			s+=a[xx][yy];
		}
		dfs(xx,yy);
		s-=a[xx][yy];
		vis[xx][yy]=0;
	}
}
int main()
{
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		memset(a,0,sizeof(a));
		for(int i=0;i<n; i++)
		{
			for(int j=0; j<m; j++)
			{
				scanf("%d",&a[i][j]);
			}
		}
		memset(vis,0,sizeof(vis));
		s=a[0][0];
		ans=s;
		dfs(0,0);
		printf("%d
",ans);
	}
	return 0;
}