무료 파이(동적 기획)(G-7)

공짜 파이
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 68704 Accepted Submission(s): 24089
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[t][x]를 구성 하 는 것 을 고려 할 수 있 습 니 다.t 초 x 번 째 위치 에 파이 가 행렬 에 채 워 져 있다 는 뜻 입 니 다.그러면 우 리 는 바닥 에서 위로 올 라 가면 지나 가 는 위치 에서 떨 어 진 파이 의 수가 가장 큰 것 이 바로 우리 가 원 하 는 것 입 니 다.
VJ 가 통과 한 코드 는 다음 과 같 습 니 다.

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int dp[200005][12];
int MAX(int a, int b, int c)
{
	int maxi;
	maxi = (a > b) ? a : b;
	return (maxi > c) ? maxi : c;
}
int main()
{
	int n, x, t;
	while (scanf_s("%d", &n) != EOF && n != 0)
	{
		int m = 0;
		memset(dp, 0, sizeof(dp));
		for (int i = 0;i < n;i++)
		{
			scanf_s("%d %d", &x, &t);
			dp[t][x]++;
			if (t > m) m = t;
		}
		for (int i = m - 1;i >= 0;i--)
		{
			for (int j = 0;j <= 10;j++)
				dp[i][j] += MAX(dp[i + 1][j], dp[i + 1][j + 1], dp[i + 1][j - 1]);
		}
		printf("%d
", dp[0][5]);
	}
}

힘 내 헤헤 헤헤!