Boj 20415) Mvp 다이아몬드

DP

백준 20415

설명

months 에는 현재 달의 등급이 들어감.

grade 에는 등급에 따른 최저 비용임.

DP?

max_v = min(grade[months[i] + 1] - 1, grade[4]);
min_v = grade[months[i]];
for(int j = 0; j < max_v; j++)
	for (int jj = 0; jj <= max_v; jj++)
		if (jj + j >= min_v && jj + j <= max_v && cache[i - 1][jj] > 0)
			cache[i][j] = max(cache[i][j], cache[i - 1][jj] + j);

점화식 안찾고 DP 비스무리한 것으로 푸는 것.

문제의 Normal 버전인 지름비용이 최대 500 으로 한정한 문제에서까지 통함.

cache[cur_month][cur_month_cost] = 누적최고액 으로 두는 방식

점화식

현재달비용 + 이전달비용 == 현재달등급 최대비용 이라는 항등식이 만족해야함.

그래서 각 달마다 현재달등급 최대비용 - 이전달비용 식을 수행해 위 항등식을 만족시킴.

그런데 이러면 등급이 내려가는 시기에는 값이 마이너스가 뜸.

이땐 이전기록 + 현재기록(마이너스임) 을 해주어서 밸런스를 맞춤.

그리고 이전기록이 j 번째 달이라고 할 때, j 대해서 다시 등급을 만족하는지 검사해서 아닐 시 j-2 에서 비용을 빼와서 j-1 에 채움(항등식을 유지시키기 위해)

이렇게 뒤로가면서 값을 빼올 때 마이너스 값이 되는경우는 DBD 같은 불가능한 경우임.

근데 이렇게 돌려막기를 해도 최대누적값에는 변화가 없어서 생략이 가능함.

그래서 위 코드에서 생략가능하다고 표시된 if 블록은 빼도 됨.

시간 복잡도

O(n)

코드

int grade[6];
int months[40];
int teer2int[128];
int cache[40];

int main()
{
	fastio;

	for (int i = 0; i < 5; i++) teer2int["BSGPD"[i]] = i;
	
	int n;
	cin >> n >> grade[1] >> grade[2] >> grade[3] >> grade[4];
	grade[5] = 1000000;
	
	for (int i = 0; i < n; i++)
	{
		static char tmp;
		cin >> tmp;
		months[i] = teer2int[tmp];
	}
	months[n] = 4;
	
	cache[0] = min(grade[months[0] + 1] - 1, grade[4]);
	for (int i = 1; i < n; i++)
	{
		cache[i] = min(grade[months[i] + 1] - 1 - cache[i - 1], grade[4]);
		if (cache[i] < 0) {
			cache[i - 1] += cache[i];
			cache[i] = 0;
			
			// 이하는 꼭 필요 없음
			for (int j = i-1; j > 1; j--)
			{
				if (cache[j] + cache[j - 1] >= grade[months[j]]) break;
				cache[j - 1] += grade[months[j]] - cache[j];
				cache[j - 2] -= grade[months[j]] - cache[j];
			}
		}
	}
	
	int ans = 0;
	for (int i = 0; i < n; i++)
		ans += cache[i];
	
	cout << ans;
}