Codeforces #206 Div1. A. Vasya and Robot

CF206はDiv1もあったけど不参加のため練習のみ。
http://codeforces.com/contest/354/problem/A

問題

1～N番の荷物が一列に並んでおり、それぞれの重さがW[i]である。
ここで２本の腕を持つロボットを使って全部の荷物を取り除きたいが、その際以下の手順でエネルギーを消費する。

• 一番左の荷物を持ち上げると、W[i]*Lのエネルギーを消費する。
• 一番右の荷物を持ち上げると、W[i]*Rのエネルギーを消費する。
• 左腕および右腕を連続で使うと、２回目以降１回毎にQL・QRのエネルギーを消費する。

W[i]およびL,R,QL,QRが与えられたとき、全荷物を取り除くまでのエネルギーを最小化せよ。

解法

まず、事前に荷物の部分和を計算しておく。
後は何個を左腕で取り除くかを0～Nまで変化させて行きながらエネルギーの最小値を計算すればよい。
i番目まで左腕で取り除くなら、(W[0]+...+W[i])*L+(W[i+1]+...+W[N-1])*Rと、あとは左腕と右腕で使う回数が多い方の腕から交互に荷物を取り除いていけばQL・QRを加算する回数もわかる。

int N,L,R,QL,QR;
int W[100001];
int T[100002];

void solve() {
	int f,i,j,k,l, x,y,N;
	
	cin>>N>>L>>R>>QL>>QR;
	FOR(i,N) cin>>W[i];
	T[0]=0;
	FOR(i,N) T[i+1]=T[i]+W[i];
	
	ll mi=1LL<<40;
	FOR(i,N+1) {
		int r=N-i;
		ll lc = T[i]*L;
		ll rc = (T[N]-T[i])*R;
		if(i>r+1) lc+=(i-(r+1))*(ll)QL;
		else if(r>i+1) rc+=(r-(i+1))*(ll)QR;
		mi=min(mi,lc+rc);
	}
	cout << mi << endl;
}

まとめ

まだAは簡単。