#include <deque>

86 阅读 0 评论 57 点赞

我是靠谱客的博主开心石头，最近开发中收集的这篇文章主要介绍#include <deque>，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

#include <deque>

Time Limit: 2 Seconds Memory Limit: 65536 KB

There is a deque of size n and you want to use it now, but unfortunately it's not empty yet. So, before using it, you're forced to do this boring work: clear it.

Each time you pop the i th number from the left side, you'll get L * wi unhappiness points. Similarly, you'll get R * wi unhappiness points if you take the i th number from the right side.

However, keep taking numbers from one side will make the work more boring. So if the previous operation is the same, you'll get qL or qR extra unhappiness points, depending on the side you take numbers from. L , R , qL and qR are all constant. Now given L , R , qL , qR and the deque, you want to know the minimum unhappiness you can get.

Input

There are multiple test cases. For each test case: the first line contains 5 integers, n , L , R , qL and qR , seperated by a single space. the second line contains n integers, the i th integer is wi (1 ≤ n ≤ 100000, 1 ≤ n , L , R , qL , qR, wi ≤ 100)

Output

For each test case, output an integer in a line, indicating your answer.

Sample Input

2 3 4 5 6
1 2
5 1 10 1 100
1 2 3 4 5

Sample Output

11
19

【分析】

题意：给一个数组，每次从左侧取数字消耗w_i ∗ l 代价，从右侧取数字消耗w_i ∗ r 代价。每次连续从左侧取额外消耗 q_l 代价，连续从右侧取额外消耗 q_r 代价。求最小代价

一段数字从某个位置切开，并且肯定是左右交替拿更小，所以拿的方案一定是LRLRLRLR(LLL/RRR...)或者RLRLRLR(LLL/RRR...)

所以求个前缀和sum

ans = min ( sum[i] * l + (sum[n] - sum[i]) * r + last * (l / r))

【代码】

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <stack>
#include <set>
#include <deque>
#include <algorithm>
#include <assert.h>
using namespace std;
#define clr(a,b) memset(a, b, sizeof(a))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define lson(x) (x << 1)
#define rson(x) (x << 1 | 1)
typedef long long LL;
typedef vector<LL> VI;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const LL mod = 1000000007;
LL powmod(LL a,LL b) {LL res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
LL gcd(LL a,LL b) { return b?gcd(b,a%b):a;}
LL mod_inv(LL a, LL k) {return powmod(powmod(a, k), mod - 2) % mod;}
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
//std::ios::sync_with_stdio(false);
// head
int sum[100100];
int main()
{
int n,l,r,ql,qr;
while(scanf("%d%d%d%d%d",&n,&l,&r,&ql,&qr) == 5)
{
sum[0] = 0;
for(int i = 1 ; i <= n ; ++i)
{
int x;scanf("%d",&x);
sum[i] = sum[i - 1] + x;
}
int ans = INF;
for(int i = 0 ; i <= n ; ++i)
{
int now = sum[i] * l + (sum[n] - sum[i]) * r;
if (n - i > i)
now = now + qr * (n - 2 * i - 1);
else
if (n - i < i)
now = now + ql * (2 * i - n - 1);
if (now < ans) ans = now;
}
printf ("%dn",ans);
}
return 0;
}