[2017-10-07] County Fair Events

링크 : https://www.acmicpc.net/problem/14780

매우 간단한 DP. 여러 개의 이벤트가 있고 각 이벤트의 시작 시간 s, 지속 시간 d가 주어졌을 때 최대한 많은 이벤트를 선택하면 된다. 이벤트 개수 제한이 10000개 밖에 안 돼서, 이벤트 시작 시간 순서대로 정렬한 다음 맨 첫 이벤트부터 그 이벤트 포함하는 경우 아닌 경우 나눠서 최대 개수 구하게 만들면 답 잘 나온다.

	#include <vector>
	#include <algorithm>
	#include <queue>
	#include <stdio.h>
	#include <map>
	#include <memory.h>
	#include <iostream>
	#include <string>
	#include <math.h>
	using namespace std;
	using ii = pair<int, int>;
	using i64 = long long int;
	using ii64 = pair<i64, i64>;
	vector<ii> events;
	int table[10001];
	int solve(int k)
	{
	if (k == events.size())
	return 0;
	if (table[k] != -1)
	return table[k];
	int& res = table[k];
	res = 1;
	res = max(res, solve(k + 1));
	for (int i = k + 1; i < events.size(); i++)
	{
	if (events[i].first >= events[k].first + events[k].second)
	{
	res = max(res, 1 + solve(i));
	break;
	}
	}
	return res;
	}
	int main()
	{
	memset(table, -1, sizeof(table));
	int n;
	scanf("%d", &n);
	events.resize(n);
	for (int i = 0; i < n; i++)
	scanf("%d %d", &events[i].first, &events[i].second);
	sort(events.begin(), events.end());
	printf("%d", solve(0));
	return 0;
	}

view raw 14780.cpp hosted with ❤ by GitHub