[原创]codeforces 354A Vasya and Robot [思维]

2016-09-07 19:32:43 Tabris_ 阅读数：530

博客爬取于2020-06-14 22:43:28
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52462508

题目链接：http://codeforces.com/contest/354/problem/A

-----------------------------------------------.

A. Vasya and Robot
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Vasya has n items lying in a line. The items are consecutively numbered by numbers from 1 to n in such a way that the leftmost item has number 1, the rightmost item has number n. Each item has a weight, the i-th item weights wi kilograms.

Vasya needs to collect all these items, however he won’t do it by himself. He uses his brand new robot. The robot has two different arms — the left one and the right one. The robot can consecutively perform the following actions:

Take the leftmost item with the left hand and spend wi · l energy units (wi is a weight of the leftmost item, l is some parameter). If the previous action was the same (left-hand), then the robot spends extra Ql energy units;
Take the rightmost item with the right hand and spend wj · r energy units (wj is a weight of the rightmost item, r is some parameter). If the previous action was the same (right-hand), then the robot spends extra Qr energy units;
Naturally, Vasya wants to program the robot in a way that the robot spends as little energy as possible. He asked you to solve this problem. Your task is to find the minimum number of energy units robot spends to collect all items.

Input
The first line contains five integers n, l, r, Ql, Qr (1 ≤ n ≤ 105; 1 ≤ l, r ≤ 100; 1 ≤ Ql, Qr ≤ 104).

The second line contains n integers w1, w2, …, wn (1 ≤ wi ≤ 100).

Output
In the single line print a single number — the answer to the problem.

Examples
input
3 4 4 19 1
42 3 99
output
576
input
4 7 2 3 9
1 2 3 4
output
34
Note
Consider the first sample. As l = r, we can take an item in turns: first from the left side, then from the right one and last item from the left. In total the robot spends 4·42 + 4·99 + 4·3 = 576 energy units.

The second sample. The optimal solution is to take one item from the right, then one item from the left and two items from the right. In total the robot spends (2·4) + (7·1) + (2·3) + (2·2 + 9) = 34 energy units.

-----------------------------------------.
题目大意 ：
就是有一排N个东西 从左到友质量分别是w1.w2。。。wn

有一个机器人搬 这个机器人有两只手 左手和右手的油耗分别是l，r ；
这个机器人正常情况下只能一只手搬一个东西之后另一只手搬 搬一个东西左手的损耗是wi* l 右手是wi*r ；
如果不换手的情况下左右手分别需要多耗油Ql，Qr ；
问搬完这么多东西最少花费是多少？

解题思路：
这道题目首先想到的是DP但是最后发现我渣不知道怎么转移
于是乎我就换了个思路 在纸上模拟了一下过程 最后发现 最后这些东西一定会有一个断点 断点的左边就是左手拿的 断点的右边就是右手拿的 这样在多想一下就发现 只要看左手拿的和右手拿的个数的差就能知道多耗费的油的个数有多少了
比如说：
7
1 2 3 4 5 6 7
比如说从某处断开
1 2 | 3 4 5 6 7
这时候左边的就是左手拿的 右边的就是右手拿的 过程可以是7 1 6 2 5 4 3 这样的话就多花费的就是 4 3 的这两个
当然你也可以 1 7 2 6 5 4 3 但这样的话多花费的就是5 4 3 这三个了 很明显不如前者好

从中也能够看出左右两边差<=1的时候是没有多的花费的
为了让多余的花费最少 所以我只要吧左右两边的错开 就能够最省了 最终多余花费也只有一边才有 另一边是不存在多余花费的
而每次都能够错开 每次多话费的也就是 两边之差-1

综上所述 这道题目就能够解了

附本题代码
-----------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
# include <bits/stdc++.h>
using namespace std;
typedef long long int LL ;
# define INF 0x3f3f3f3f
const int M = 1e5+12;

int a[M],suml[M],sumr[M];

int abs (int a)
{
    if(a>=0)
        return a;
    else
        return -a;
}

int main()
{
    ios::sync_with_stdio(false);
    int n,l,r,ql,qr;
    while( cin>>n>>l>>r>>ql>>qr )
    {
        suml[0]=0,sumr[n+1]=0;
        for(int i=1; i<=n; i++)
        {
            cin>>a[i];
            suml[i]=suml[i-1]+a[i];   //前缀和
        }
        for(int i=n; i; i--)
            sumr[i]=sumr[i+1]+a[i];   //后缀和

        int mini=1<<30,tem;
        for(int i=0; i<=n; i++)
        {
            //( (l-r)>0?(l-r)*ql:0 )+ ( (r-l)>0?(r-l)*qr:0 )
            //(i-1>n-i)?((i-1)-(n-i))*qr:((n-i)-(i-1))*ql

            if(abs(i*2-n)<=1)        tem = 0;
            else if(i>n-i)      tem = ql*(i*2-n-1);  /*左右 之差 在1 的位置是不算的*/
            else                tem = qr*(n-2*i-1) ;

            mini=min(mini,suml[i]*l + sumr[i+1]*r + tem );
            //cout<<suml[i]*l<<"  "<<sumr[i+1]*r<<"  "<<tem<<endl;
        }
        cout<<mini<<endl;
    }
    return 0;
}