글 읽기 - 반례를 못찾겠습니다..

leekh2002 4년 전 0

dp[i] -> i번째까지 잡을수 있는 최대 개수

dp[i]=max(dp[i],j = (0,1,2..i-1)에서 i까지 시간안에 올 수 있는경우, dp[j] + 1)

두더지 정보를 T기준으로 정렬하고,

이런식으로 풀어봤는데 어떤 경우에서 반례가 발생하는지 모르겠어요..

#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;
int main()
{
	int i, dp[6669] = { 0 }, j, res = 0, n;
	double  s;
	pair<double, pair<double, double>> inf[6669];

	scanf("%d%lf", &n, &s);

	for (i = 1; i <= n; i++)
		scanf("%lf%lf%lf", &inf[i].second.first, &inf[i].second.second, &inf[i].first);
	inf[0].first = inf[0].second.first = inf[0].second.second = 0;
	sort(inf, inf + n + 1);
	for (i = 0; i <= n; i++)
	{
		for (j = 0; j < i; j++)
		{
			double dx = inf[i].second.first - inf[j].second.first, dy = inf[i].second.second - inf[j].second.second;
			if (sqrt((dx * dx) + (dy * dy)) <= (inf[i].first - inf[j].first) * s)
				dp[i] = max(dp[i], dp[j] + 1);
		}
		res = max(res, dp[i]);
	}
	printf("%d\n", res);

	return 0;
}

dabbler1 1년 전 1

출발점에서 어떤 두더지로 시간 내에 못가는데 그 두더지에서 다른 두더지로는 갈수 있을때 문제가 생깁니다

1
100 1
100 2
# 정답 0, 오답 1

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 못찾겠습니다..

leekh2002 4년 전 0

dabbler1 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말