Codeforces #206, Division 1, A ( Division 2, C ) : Vasya and Robot

問題文

http://codeforces.com/contest/355/problem/C

概要

横一列に N 個のアイテムが並んでいて、これらをロボットを使って全て集めたい。
ロボットは次の行動ができる。

• 残っている内で左端のアイテムをコスト l * w で取得する。直前と同じ動作である場合、さらに Ql のコストがかかる
• 残っている内で右端のアイテムをコスト r * w で取得する。直前と同じ動作である場合、さらに Qr のコストがかかる

ここで、w は取得するアイテムの重さである。

n, l, r, Ql, Qr 及び、各アイテムの重さが与えられる。
必要なコストの最小値を求めよ。

解法

端からしか取得できないので、列をある部分で区切れば、左側を l 、右側を r で処理することになります。
区切る位置が決まったとき、追加でない方のコストは、そこに含まれるアイテムの重みの総和に l か r を乗じた値になります。
追加のコストは処理する数の差が 1 以下であれば、適当な順序で処理をすることで 0 にできます。
そうでないとき、( 差 - 1 ) * Q のコストがかかります。

区切る位置が決まったときの計算方法が分かったので、区切る位置を全て試せば解くことができます。
ただし、重みの総和を毎回一から計算すると になって間に合わなくなるので、保持しておいて区切る位置をずらすときに更新するようにします。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n, l, r, ql, qr;
	cin >> n >> l >> r >> ql >> qr;
	
	VI ws( n );
	FOR( w, ws )
	{
		cin >> w;
	}

	int res = INT_MAX, twl = 0, twr = accumulate( ALL( ws ), 0 );
	REP( i, 0, n + 1 )
	{
		const int L = i, R = n - L;
		int tmp = twl * l + twr * r;
		if ( L + 1 < R )
		{
			tmp += ( R - L - 1 ) * qr;
		}
		else if ( R + 1 < L )
		{
			tmp += ( L - R - 1 ) * ql;
		}
		res = min( res, tmp );

		if ( i < n )
		{
			twl += ws[i];
			twr -= ws[i];
		}
	}

	cout << res << endl;

	return 0;
}