Codeforces 355 C戦略問題

タイトルリンク:http://codeforces.com/problemset/problem/355/C
タイトル:
n個のバーベルの重量を与え、すべてのバーベルを1回持ち上げるのに必要な最小エネルギーを聞く.
1、毎回一番左か一番右のバーベルしか挙げられない
2、バーベルを1つ挙げると左手か右手でwi*l(wi*r)
3、今度は左手を使い、前回も左手を使うとQlのエネルギーがかかります.右手を使い続けるとQrがかかります
明らかに私たちは最後にバーベルを挙げて、iに設定します. 
[1,i-1]を挙げたバーベルはすべて左手,[i+1,n]を挙げたものはすべて右手で,ここで費やした基礎エネルギーは接頭辞と求めることができる.
i番目には
1、左手で持ち上げる
2、右手で持ち上げる
このときの基礎エネルギーは、費用を最小限に抑えるために、片手を連続的に使用する場合はできるだけ小さく、交互に使用することが最も少ないことが明らかになった.
暴力列挙は最後にi番目のバーベルと左手か右手でこのバーベルを挙げればよい

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <math.h>
#include <set>
#include <vector>
#include <queue>
using namespace std;
#define N 100005
#define ll __int64
#define eps 1e-7
#define inf 1029385391204938
bool equ(double x, double y=0.0){return ((x-y>0)?x-y:y-x)<eps;}
ll n, m;
ll l, r, ql, qr;
ll a[N];
ll sum[2][N];
ll Sum(ll cur, ll x, ll y){return sum[cur][y]-sum[cur][x-1];}
int main(){
	ll i, j, k, d;
	while(~scanf("%I64d %I64d %I64d %I64d %i64d",&n, &l,&r,&ql,&qr)){
		memset(sum, 0, sizeof sum);
		for(i = 1; i <= n; i++)scanf("%I64d",&a[i]);
		for(i = 1; i <= n; i++)
		{
			sum[0][i] = a[i]*l;
			sum[1][i] = a[i]*r;
		}
		for(i = 1; i <= n; i++)
		{
			sum[0][i] += sum[0][i-1];
			sum[1][i] += sum[1][i-1];
		}

		ll ans = inf;
		for(i = 1; i <= n; i++)
		{
			ll now = 0;//          
			now += Sum(0, 1, i);
			now += Sum(1,i+1, n);
			ll lt = i, rt = n-i;
			if(lt>rt)lt-=rt, rt=0;
			else rt-=lt, lt = 0;
			if(lt)lt--; else if(rt)rt--;
			now += lt*ql + rt*qr;

			ans = min(ans, now);
		}
		for(i = 1; i <= n; i++)
		{
			ll now = 0;//          
			now += Sum(0, 1, i-1);
			now += Sum(1,i, n);
			ll lt = i-1, rt = n-i+1;
			if(lt>rt)lt-=rt, rt=0;
			else rt-=lt, lt = 0;
			if(lt)lt--; else if(rt)rt--;
			now += lt*ql + rt*qr;

			ans = min(ans, now);
		}
		printf("%I64d
",ans);
	}
	return 0;
}
/*
3 4 4 19 1
42 3 99

4 7 2 3 9
1 2 3 4

*/