Educational round #73 D - Make the fence great again (dp)

https://codeforces.com/contest/1221/problem/D

 

한 부분 당 최대 2만큼 늘릴 수 있다는 것을 가정하고 dp모양은 만들었지만 예외가 있을 거라 생각하고 삽질함..

 

i==0일 떈 그냥 0~2번 다 확인해주고

i>0 일 떈 i-1의 상태와만 비교해주고 인자로 본인이 얼마나 늘렸는지만 같이 넘겨주면 된다.

 

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MAX = 3e5 + 1;
const ll INF = 1e18 + 1;

int n;
ll dp[MAX][3];
int h[MAX], c[MAX];

ll f(int k, int x) {
	if (k == n) return 0;
	
	ll& ret = dp[k][x];
	if (dp[k][x] != -1) return ret;

	ret = INF;
	for (ll i = 0; i < 3; i++)
		if (k == 0 || h[k] + i != h[k - 1] + x)
			ret = min(ret, f(k + 1,i) + i * c[k]);

	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int q; cin >> q;
	while (q--) {
		cin >> n;
		for (int i = 0; i < n; i++)
			cin >> h[i] >> c[i];

		for (int i = 0; i <= n; i++)
			dp[i][0] = dp[i][1] = dp[i][2] = -1;
		
		cout << f(0, 0) << '\n';
		
	}
}