!HDU 1176-DP--(매트릭스 게이지)

제목: 0부터 10까지 소명부터 5라는 위치에 있는 수축이 있다.이제 하늘에서 호떡이 떨어지기 시작했다. 샤오밍은 매번 단위 1의 길이만 이동할 수 있으니 샤오밍이 호떡을 얼마나 많이 받을 수 있는지 구해 보자.
분석: 처음에 동적 기획을 접했고 규범에 맞는 사고를 제대로 이해하지 못했기 때문에 처음에 dp 방법이 맞는지 모르겠지만 TLE가 되었다.정확한 방법은 시간을 줄로 하는 행렬을 만드는 것이다. 최초의 맵[i][j]은 i시간에 j위치에서 떨어진 파이의 수량을 대표하고 상태 이동 방정식은 맵[i][j]=map[i][j]+max(map[i+1][j-1], 맵[i+1][j], 맵[i+1], 맵[i+1][j+1][j+1])이다.맨 밑에서부터 위로 하는 거야.dp는 모두 결과에 가장 가까운 위치에서 앞으로 밀어붙여 최종적으로 가장 좋은 결과를 얻은 것 같다.더욱 깊이 이해해야 한다.
코드:

#include
#include
using namespace std;
int map[100008][12];
int n;
int main()
{
	int a,b;
	while(cin>>n&&n){
		int m=0;
		memset(map,0,sizeof(map));
		for(int i=0;i>a>>b;
			map[b][a]++;
			if(m=0;i--){
			for(int j=1;j<10;j++){
				int tmp=map[i+1][j-1]>map[i+1][j]?map[i+1][j-1]:map[i+1][j];
				int mx=tmp>map[i+1][j+1]?tmp:map[i+1][j+1];
				map[i][j]+=mx;
			}
		    map[i][0]+=map[i+1][0]>map[i+1][1]?map[i+1][0]:map[i+1][1];
		    map[i][10]+=map[i+1][9]>map[i+1][10]?map[i+1][9]:map[i+1][10];
		}
		cout<