18186번 : 라면 사기 (Large)

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

18186번: 라면 사기 (Large)

18185번과 매우 유사한 문제다.

2022.01.09 - [sunrin] - 18185번 : 라면 사기 (Small)

아이디어 : 

다만, 한가지가 다르다. B와 C가 주어졌는데,
18185에서는 비용이 3, 5, 7로 연속3개의 공장에서 사는게 무조건 이득이었다.

하지만, 18186에서는 2, 1002, 2002 이런식으로 주어질 수도 있다.
즉, 모든 라면을 B로 사는 케이스가 최적일 수도 있다는 소리다.

구현 : 

B*2<=B+C이면 모든 라면을 B로 사는게 좋다.

코드 :

 

#include <bits/stdc++.h>
#define min3(a,b,c) min((a),min((b),(c)))
using namespace std;
using ll=long long int;
vector<ll> v;
struct node {
	ll a, b, c; // 비용 B, 비용 B+C, 비용 B+2C
	node(ll a, ll b, ll c):a(a),b(b),c(c){}
};
int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int N, B, C; cin>>N>>B>>C;
	for(int i=0; i<N; ++i){
		ll a; cin>>a; v.push_back(a);
	}
	ll res=B*v[0];
	if(B*2<=B+C){
		res=0;
		for(int i=0; i<N; ++i){
			res+=v[i]*B;
		}
		cout << res << '\n';
		return 0;
	}
	node prev2(0,0,0); // i-1
	node prev1(v[0],0,0); // i
	for(int i=0; i<N-1; ++i){
		node prev0(0,0,0); // i+1
		// 1. prev1에서 비용 B으로 산거 일부를 prev0과 함께 비용 B+C로 계산한다.
		ll k=min(prev1.a, v[i+1]);
		res-=B*k;
		res+=(B+C)*k;
		prev1.a-=k;
		v[i+1]-=k;
		prev1.b+=k;
		prev0.b+=k;
		// 2. prev2와 prev1에서 비용 B+C로 산거 일부를 prev0과 함께 비용 B+C+C로 계산한다.
		if(i!=0){
			ll k=min3(prev2.b, prev1.b, v[i+1]);
			res-=(B+C)*k;
			res+=(B+C+C)*k;
			prev2.b-=k;
			prev1.b-=k;
			v[i+1]-=k;
			prev2.c+=k;
			prev1.c+=k;
			prev0.c+=k;
		}
		// 3. 남은걸 prev0에 비용 B으로 산다.
		prev0.a+=v[i+1];
		res+=B*v[i+1];
		prev2=prev1;
		prev1=prev0;
	}
	cout << res << '\n';
}