[boj : 2651]자동차경주대회

www.acmicpc.net/problem/2651

2651번: 자동차경주대회

문제 : 도착지점까지 정비소에 들려 최소의 시간으로 도착할 수 있는 케이스를 구해라

 

풀이 : LIS의 응용버전

1)각 정비소간 거리를 prefix 로 담아준다.

2)O(n^2)의 시간복잡도를 활용하여 정비소간 차이가 D(정비소에 들렸을때 최대로 갈 수 있는 거리) 이하이고 시간이 더 적게 걸릴때 업데이트, 또한 지금까지 거쳐온 정비소의 번호를 기록해 둔다.

3)지나온 자취를 역추적

+

데이터 추가로 코드 수정(int->long long)으로 경계값 입력시 다른 답을 도출했기 때문

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

ll arr[110], Time[110], prefix[110];
ll A[110], B[110];
vector<ll> v;

ll solve(ll x);

int main()
{
	ll d, n;
	cin >> d >> n;
	for (ll i = 1; i <= n + 1; i++) {
		cin >> arr[i];
		prefix[i] = prefix[i - 1] + arr[i];
		A[i] = (ll)10e9;
	}
	for (ll i = 1; i <= n; i++) {
		cin >> Time[i];
	}
	for (ll i = 1; i <= n + 1; i++)
		if (prefix[i] <= d)
			A[i] = Time[i];
	for (ll i = 1; i <= n + 1; i++) {
		for (ll j = 1; j < i; j++)
		{
			if (prefix[i] - prefix[j] <= d && A[i] > A[j] + Time[i]) {
				B[i] = j;
				A[i] = A[j] + Time[i];
			}
		}
	}
	ll r = solve(n + 1);
	cout << A[n + 1] << "\n" << v.size() << "\n";
	for (ll u : v)
		cout << u << " ";
	return 0;
}
ll solve(ll x)
{
	if (B[x] == 0)return x;
	ll ret = solve(B[x]);
	v.push_back(ret);
	return x;
}