[문제풀이] 루구 2120: [ZJOI 2007] 창고 건설

14358 단어 문제풀이LuoGuDP기울기 최적화
원제 전송문 초학 경사율 최적화 좋은 문제 먼저 O(n2)O(n^2)O(n2)DP예처리si=∑j=1ixjpj,spi=∑j=1ipjsi=\sum_{j=1}^{i}x_jp_j,sp_i=\sum_{j=1}^{i}p_jsi = ∑j=1i xj pj,spi = ∑j=1i pj 전이 방정식: dp [i] = m i n(dp j - 4s i + s j + x i(sp i: 4s p j)) + c i dp [i] =min(dp j-s i+s j+x i(sp j)) + ci dp[i]=min(dpj​−si​+sj​+xi​(spi​−spj​))+ci​
두 가지 의사결정을 고려하면 x, yx, y, 만족x>yx>yx>y 만약 x가 y보다 뒤떨어지고 y보다 우수하다면 dp x: 즉 s i + s x + x x i (sp i - s p x) < d p y - s i + s y + x i (s p i - s p y) dpx-s_i+s_x+x_i(sp_i-sp_x)Code: 
#include 
#define maxn 1000010
#define LL long long
using namespace std;
LL n, s[maxn], sp[maxn], c[maxn], dp[maxn], q[maxn], x[maxn];

inline LL read(){
	LL s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

double slope(int x, int y){ return 1.0 * (dp[x] + s[x] - dp[y] - s[y]) / (sp[x] - sp[y]); }

int main(){
	n = read();
	for (int i = 1; i <= n; ++i){
		x[i] = read(), sp[i] = read(), c[i] = read();
		s[i] = s[i - 1] + x[i] * sp[i], sp[i] += sp[i - 1];
	}
	int h = 0, t = 0;
	for (int i = 1; i <= n; ++i){
		while (h < t && slope(q[h + 1], q[h]) < x[i]) ++h;
		dp[i] = dp[q[h]] - s[i] + s[q[h]] + x[i] * (sp[i] - sp[q[h]]) + c[i];
		while (h < t && slope(q[t], q[t - 1]) > slope(i, q[t])) --t;
		q[++t] = i;
	}
	printf("%lld
", dp[n]);
	return 0;
}
Django C.R.U.D (2) - westarbucks
크롬이든 Powerherll이든 Openssl equivalent의 AES를 사용할 수 있습니다

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage