[2017-10-07] The County Fair

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

그다지 어려운 문제가 아니었는데 문제 해석이 잘 안 돼서 한참 끙끙댔다. n개의 도시가 있고 첫 도시에서 시작해서 pi시간에 어떤 도시에 있을 수 있으면 그 도시에서 수여하는 상을 받을 수 있고, n개 도시 각각에 대해 움직이는데 걸리는 시간이 주어졌을 때 최대한 받을 수 있는 상 개수를 구하는게 문제다. 처음에 도시 개수 * 최대 시간 으로 모든 도시 왔다갔다하는거 다 계산하는 DP를 생각했는데 이러면 최대 시간 범위가 100만이라 시간 초과가 난다. 좀 더 생각하면 줄일 수 있는데, 각 도시에 대해 그냥 그 도시에서 수여하는 상 받을 지 아닐 지만 고민하면 되고, 이건 어떤 도시에 p[i]보다 일찍 도착한 다음 p[i]까지 기다리면 그 도시에서 수여하는 상 받을 수 있는 거기 때문에 이를 이용해서 간단하게 O(N^2) DP를 짤 수 있다. N 범위가 400이라 충분.

	#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>;
	int n;
	int p[401];
	int times[401][401];
	int table[401];
	int maxPrize(int k)
	{
	if (table[k] != -1)
	return table[k];
	int& res = table[k];
	res = 1;
	for (int i = 0; i < n; i++)
	{
	if (i == k)
	continue;
	if (p[k] + times[k][i] <= p[i])
	res = max(res, 1 + maxPrize(i));
	}
	return res;
	}
	int main()
	{
	memset(table, -1, sizeof(table));
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	scanf("%d", &p[i]);
	for (int i = 0; i < n; i++)
	for (int j = 0; j < n; j++)
	scanf("%d", &times[i][j]);
	int ans = 0;
	for (int i = 0; i < n; i++)
	if (times[0][i] <= p[i])
	ans = max(ans, maxPrize(i));
	printf("%d", ans);
	return 0;
	}

view raw 14777.cpp hosted with ❤ by GitHub