[백준] 4008 특공대 - C++

https://www.acmicpc.net/problem/4008

---

CHT의 바이블

 

점화식은 $DP[i] = max(\;a(S[i]-S[j])^{2}+b(S[i]-S[j] ) +c+DP[j]\;)$ 이다.

$j$와 관련 없는 항은 $max$밖으로 빼줄 수 있다.

$(S[i]-S[j])^{2}$를 전개한 뒤 &max& 밖으로 항을 빼주자.

그럼 $DP[i] = max(\;-2aS[i]S[j] + aS[j]^{2} - bS[j] + DP[j]\;) + aS[i]^{2} + bS[i] + c$이 되고,

$max$ 밖의 항들은 상수항이므로 나중에 더해줘도 된다.

$max$ 안의 식은 $S[i]$에 대한 일차식으로 나타낼 수 있다.

따라서 $DP[i] = max(\;-2aS[j]x + (aS[j]^{2}-bS[j]+DP[j])\;) + Constant$ 이고,

일차식의 기울기는 $-2aS[j]$, y절편은 $aS[j]^{2}-bS[j]+DP[j]$임을 알 수 있다.

 

이를 이용해 CHT를 짜주자.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
const int MAX = 1'000'005;

struct Line {
	ll m, b; //기울기, y절편
	db start; //스타트포인트 (반직선형태)
};

ll a, b, c;
vector<ll>s(MAX), dp(MAX);
vector<Line>hull;

db cross(Line& a, Line& b) { //두 직선의 교점의 x좌표를 구하는 함수
	return (db)(a.b - b.b) / (db)(b.m - a.m);
}
ll constant(ll i) {
	return a * s[i] * s[i] + b * s[i] + c;
}
ll m(ll j) {
	return 1LL * -2 * a * s[j];
}
ll k(ll j) {
	return (1LL * a * s[j] * s[j]) - (1LL * b * s[j]) + (1LL * dp[j]);
}

int main() {
	int n;
	cin >> n;

	cin >> a >> b >> c;
	for (int i = 1; i <= n; i++) {
		ll x;
		cin >> x;
		s[i] = s[i - 1] + x;
	}

	int idx = 0;

	for (int i = 1; i <= n; i++) {
		dp[i] = constant(i); //상수항

		if (!hull.empty()) {
			while (idx + 1 < hull.size() && hull[idx + 1].start < s[i]) {
				idx++;
			}
			dp[i] = max(dp[i], hull[idx].m * s[i] + hull[idx].b + constant(i));
		}
		Line l = { m(i), k(i), 0 };

		while (!hull.empty()) {
			l.start = cross(hull.back(), l);
			if (hull.back().start < l.start) {
				break;
			}
			hull.pop_back();
		}
		hull.push_back(l);
	}
	cout << dp[n];
	return 0;
}

idx는 j의 역할을 해준다.

---

점화식을 일차식 형태로 바꾸는게 너무 힘들었다...

---