(백준) 14501 떠나는 2

문제

상담사로 활동 중인 백준이 사퇴를 앞두고 있다.

오늘부터 N+1일에 퇴사하기 위해 남은 N일 동안 최대한 많은 상담을 하려고 노력합니다.

백준이는 비서에게 가능한 한 많은 상담 일정을 잡아달라고 부탁했고 비서는 하루에 한 명씩 다른 사람들과 상담을 예약했다.

각 상담은 상담을 완료하는 데 걸리는 기간 Ti와 상담 시 받을 수 있는 금액 Pi로 구성됩니다.

N=7인 경우 다음 상담 일정을 고려한다.

1일 2일 3일 4일 5일 6일 7일 티피

1일 예정된 상담은 총 3일이 소요되며, 상담 시 받을 수 있는 금액은 10일입니다.

5일 예정인 상담은 총 2일이 소요되며 받을 수 있는 금액은 15입니다.

상담에 소요되는 기간은 하루 이상 소요될 수 있기 때문에 모든 상담이 가능한 것은 아닙니다.

예를 들어 1일에 상담을 했다면 2일과 3일에는 상담을 할 수 없습니다.

2일 상담이 있는 경우 3, 4, 5, 6일 예정된 상담은 진행하실 수 없습니다.

그리고 N+1일은 회사에 없어서 6일이나 7일은 상담을 못해요.

퇴사 전 상담의 최대 혜택은 1일, 4일, 5일에 상담을 받는 것이며 이때의 혜택은 10+20+15=45입니다.

상담이 제대로 이루어졌을 때 백준이 얻을 수 있는 최대 이익을 찾는 프로그램을 작성하세요.

입력

첫 번째 줄은 N(1 ≤ N ≤ 1,500,000)을 나타냅니다.

2번째 줄부터 N번째 줄까지는 Ti, Pi를 공백으로 구분하여 1번째부터 N번째까지 순서대로 부여한다.

(1 ≤ Ti ≤ 50, 1 ≤ 파이 ≤ 1,000)

인쇄

첫 번째 줄에 백준이 얻을 수 있는 최대 이익을 출력하세요.

2개의 테이블을 만듭니다.

DP 테이블은 현재 날짜 협의 시점의 최대값이며,

M 테이블은 현재 날짜의 협의와 상관없이 최대값입니다.

M 테이블은 TEMP 값으로 업데이트됩니다.

DP(N)=P(N)+DP(NT(i))이고,

TEMP=최대(TEMP,DP(N))

M(N)=온도

안돼.

M(1)을 출력하면 됩니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy() = { -1,0,1,0 }, dx() = { 0,1,0,-1 }, INF = 987654321;

using namespace std;

int N, T(1500001), P(1500001), dp(1500001), M(1500001), MAX = -1, TEMP = 0;
int main() {
	FAST;
	cin >> N;
	REP(i, N)
		cin >> T(i) >> P(i);
	for (int i = N; i >= 1; i--) {
			if(i+T(i)-1<=N)
				dp(i) = P(i);
			dp(i) += M(i + T(i));
			TEMP = max(dp(i), TEMP);
			M(i) = TEMP;
	}
	cout << M(1);
}