boj, 백준) 12008. 262144

https://www.acmicpc.net/problem/12008

12008번: 262144

이 문제는 생각해보면 구조가 토너먼트?랑 비슷하단것을 알 수 있습니다. 토너먼트 형태의 문제는 대표적으로 https://www.acmicpc.net/problem/11066 (파일 합치기) 가 있습니다. 이런문제는 dp[i][j]를 i에서 j로 얻을 수 있는 최대 이런식으로 정의하면 풀 수 있습니다. 이 문제에서도 처음에 dp[i][j]를 i에서 j를 모두 사용해 만들 수 있는 최대로 정의하고 만약에 만들 수 없으면 0을 정의하는식으로 생각했는데 다시보니깐 dp[i][j] 값이 있는 것들만 관리해주면 돼서 벡터 dp[i] 에 커지는 j들만 추가하는식으로 관리해줬습니다. 

 

#include <bits/stdc++.h>
using namespace std;

int N;
int arr[270000];

vector<int> dp[270000];

void go(int x) {
	dp[x].push_back(x);
	if (x == N) return;
	int y = x + 1;
	int xx = arr[x];
	while (1) {
		if (xx < arr[y]) return;
		if (xx > arr[y] + dp[y].size() - 1) return;
		int k = xx - arr[y];
		int i = dp[y][k];
		dp[x].push_back(i);
		y = i + 1;
		xx++;
		if (y > N) return;
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
	for (int i = N; i >= 1; i--) {
		go(i);
	}
	int M = 0;
	for (int i = 1; i <= N; i++) {
		int t = dp[i].size();
		M = max(M, arr[i] + t - 1);
	}
	cout << M;
}