Minimal Cost

2024-01-04 08:38

文章标签 cost minimal

本文主要是介绍Minimal Cost，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：
There is a graph of n rows and 106+2 columns, where rows are numbered from 1 to n and columns from 0 to 106+1:

Let’s denote the node in the row i and column j by (i,j).

Initially for each i the i-th row has exactly one obstacle — at node (i,ai). You want to move some obstacles so that you can reach node (n,106+1) from node (1,0) by moving through edges of this graph (you can’t pass through obstacles). Moving one obstacle to an adjacent by edge free node costs u or v coins, as below:

If there is an obstacle in the node (i,j), you can use u coins to move it to (i−1,j) or (i+1,j), if such node exists and if there is no obstacle in that node currently.
If there is an obstacle in the node (i,j), you can use v coins to move it to (i,j−1) or (i,j+1), if such node exists and if there is no obstacle in that node currently.
Note that you can’t move obstacles outside the grid. For example, you can’t move an obstacle from (1,1) to (0,1).
Refer to the picture above for a better understanding.

Now you need to calculate the minimal number of coins you need to spend to be able to reach node (n,106+1) from node (1,0) by moving through edges of this graph without passing through obstacles.

Input
The first line contains a single integer t (1≤t≤104) — the number of test cases.

The first line of each test case contains three integers n, u and v (2≤n≤100, 1≤u,v≤109) — the number of rows in the graph and the numbers of coins needed to move vertically and horizontally respectively.

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤106) — where ai represents that the obstacle in the i-th row is in node (i,ai).

It’s guaranteed that the sum of n over all test cases doesn’t exceed 2⋅104.

Output
For each test case, output a single integer — the minimal number of coins you need to spend to be able to reach node (n,106+1) from node (1,0) by moving through edges of this graph without passing through obstacles.

It can be shown that under the constraints of the problem there is always a way to make such a trip possible.

Example
inputCopy
3
2 3 4
2 2
2 3 4
3 2
2 4 3
3 2
outputCopy
7
3
3
Note
In the first sample, two obstacles are at (1,2) and (2,2). You can move the obstacle on (2,2) to (2,3), then to (1,3). The total cost is u+v=7 coins.

In the second sample, two obstacles are at (1,3) and (2,2). You can move the obstacle on (1,3) to (2,3). The cost is u=3 coins
题解：
每行只有一个障碍物，并且障碍物不在第一列和最后一列，所以分三种情况
1：有一行的障碍物距离大于等于2，则不需要挪动
2：障碍物都在同一列，则需要挪动u+v
3:不都在同一列，则可以u+v或者同行移动两格

#include <bits/stdc++.h>
using namespace std;
long long a[105];
int main()
{int t;cin>>t;while(t--){long long n,u,v;cin>>n>>u>>v;int ret=1;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);if(a[i]!=a[i-1]&&i!=1) ret=0;}long long ans=0;int f=0;for(int i=1;i<=n;i++){if(abs(a[i]-a[i+1])>=2&&i!=n){ans=0;f=1;break;}}if(!f){if(ret) ans=min(u+v,2*v);else ans=min(u,v);}cout<<ans<<endl;}return 0;
}