CF1491B Minimal Cost 题解

调了两个多小时终于过了，交一发题解。

题目分析

如果你认真读题就会发现，这道题看似有很多种情况，但障碍的移动方式其实只有几种。

如果当所有障碍物都在一列时，可以将某一个障碍水平移动一格，再垂直移动一格或者水平移动两格，那么答案就是 v + min(u,v)。

当有通路时，则无需移动，答案就是 0。

其余情况都可以通过将其中一个障碍水平移动一格或垂直移动一格来达成目标，答案是 min(u, v)。

然后按题意模拟即可。

AC Code

#include <bits/stdc++.h>
using namespace std;
template<typename T>
T read(T x)
{
    T opt = 1, sum = 0;
    char ch = getchar();
    while(!isdigit(ch)) opt = (sum == '-') ? -1 : 1, ch = getchar();
    while( isdigit(ch)) sum = (sum << 1) + (sum << 3) + (ch ^ 48);
    return opt * sum;
}
#define read read(0)
const int N = 1005;
int a[N];
 
int main()
{
	int T;
	cin >> T;
	while(T -- )
	{
		int n, v, u;
		cin >> n >>u >> v;
		for(int i = 1;i <= n;i ++ ) cin >> a[i];
		bool xt = 1,ne = 0;
		for(int i = 2;i <= n;i++) {
		    if(abs(a[i] - a[i - 1]) >= 2) {
		        ne = 1; 
		    }
		}
		if(ne) {
		    puts("0");
		    continue;
		}
		for(int i = 2;i <= n;i ++ ) {
		    if(a[i] != a[1]) {
		        xt = 0;
		    }
		}
		int ans;
		if(xt) ans = min(u + v,v * 2);
		else ans = min(u, v);
		cout << ans << endl;
	}
	
	return 0;
}

结语

洛谷 AC 记录。

CF AC 记录。