HDU 1176 무료 파이

공짜 파이
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 52921    Accepted Submission(s): 18575
Problem Description
하늘 에 서 는 파이 가 떨 어 지지 않 는 다 고 하 는데 어느 날 gameboy 가 집 으로 돌아 가 는 오솔길 을 걷 고 있 는데 갑자기 하늘 에서 파이 가 한 움큼 떨 어 졌 다.말하자면 gameboy 의 인품 은 정말 좋 습 니 다.이 파 이 는 다른 곳 에서 도 떨 어 지지 않 고 그의 옆 에 있 는 10 미터 범위 안에 떨 어 졌 습 니 다.파이 가 바닥 에 떨 어 지면 당연히 먹 을 수 없 기 때문에 gameboy 는 바로 몸 에 있 는 가방 을 벗 고 받 았 다.그러나 오솔길 양쪽 에 사람 이 서 있 을 수 없 기 때문에 그 는 오솔길 에서 만 연결 할 수 있다.게 임 보이 가 평소 방 에 틀 어 박 혀 게임 을 하기 때문에 게임 에 서 는 날렵 한 고수 이지 만 현실 에 서 는 운동신경 이 무 뎌 1 초 에 1m 를 넘 지 않 고 움 직 이 는 범위 내 에서 만 추락 하 는 파 이 를 받 을 수 있다.현재 이 작은 길 을 아이콘 에 좌표 로 표시 합 니 다:
문 제 를 간소화 하기 위해 다음 시간 동안 파이 가 0-10 이라는 11 개의 위치 에 떨어진다 고 가정 한다.처음에 gameboy 는 5 자리 에 서 있 었 기 때문에 1 초 에 그 는 4,5,6 세 자리 중 한 자리 에 있 는 파 이 를 받 을 수 밖 에 없 었 다.게 임 보이 에 게 파 이 를 최대 몇 개 받 을 수 있 냐 고 물 었 다.그의 가방 이 끝 없 이 많은 파 이 를 수용 할 수 있다 고 가정 하 자)
 
Input
입력 데이터 가 여러 그룹 입 니 다.각 조 데이터 의 첫 번 째 행 위 는 정수 n(0)이다.
 
Output
각 그룹의 입력 데 이 터 는 한 줄 의 출력 에 대응 합 니 다.전체 m 를 출력 하면 gameboy 가 최대 m 개의 파 이 를 받 을 수 있 음 을 나타 낸다.
알림:이 문제 의 입력 데 이 터 는 양 이 많 습 니 다.scanf 로 읽 는 것 을 권장 합 니 다.cin 으로 시간 을 초과 할 수 있 습 니 다.
 
Sample Input

  
    
    
    
    

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

 
Sample Output

  
    
    
    
    

     
     
     
     
   4
  
    
    
    
    

 
분석:퇴적 탑 과 유사 한 그 제목,아주 간단 한 dp,설명 하지 않 고 코드 를 직접 붙 입 니 다.

#include
#include
#include
#include
#include
#include
using namespace std;

int MAX(int a,int b,int c)
{
	int mm=max(a,b);
	int ans=max(mm,c);
	return ans;
}

int dp[100005][15];

int main()
{
	int n;
	int t,x;

	while(scanf("%d",&n),n)
	{
		memset(dp,0,sizeof(dp));
		for(int i=0;i=0;i--)
		{
			for(int j=0;j<11;j++)
			{
				if(j==0)
					dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]);
				else if(j==10)
					dp[i][j]+=max(dp[i+1][j],dp[i+1][j-1]);
				else
					dp[i][j]+=MAX(dp[i+1][j],dp[i+1][j-1],dp[i+1][j+1]);
			}
		}
		printf("%d
",dp[0][5]);
	}
	
	return 0;
}