読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Codeforces #206 Div1. A. Vasya and Robot

Codeforces

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

問題

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

  • 一番左の荷物を持ち上げると、W[i]*Lのエネルギーを消費する。
  • 一番右の荷物を持ち上げると、W[i]*Rのエネルギーを消費する。
  • 左腕および右腕を連続で使うと、2回目以降1回毎に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は簡単。

広告を非表示にする