Berserk And Fireball

发表于 分类于 ，

    有 n 个战士站成一排，第 i 个战士的战力是 ai。所有战士的战力都是两两不同的。

    你可以使用两种类型的咒语：

    1. 火球术：你可以消耗 x 点法力值来干掉连续的 k 个战士（你必须干掉正好 k 个，而不能干掉 ≤k 个）。

    2. 狂暴术：你可以消耗 y 点法力值，选择站在一起的两个战士使他们展开决斗，战力较弱的那个战士将会被干掉。

    我们来举个例子，假设有 7 个战士，其战力分别为 [2,3,7,8,11,5,4]，且此时的k=3（k 的定义详见火球术）。如果你对战力为 8 与 11 的两个战士施加狂暴术，剩下战士的战力将会变成 [2,3,7,11,5,4]（战力为 8 的战士在决斗中战死）。然后如果我们对战力为 [7,11,5] 的战士施加火球术，剩下战士的战力将会变成 [2,3,4]。

    你想要组建一支军队，因此你想要将所有战士战力的序列从 a1,a2,⋯,an 变为 b1,b2,⋯,bm。试计算你所需的最少法力值。

    输入格式

    第一行两个整数 n,m(1≤n,m≤2⋅105) ——序列 a 的长度和序列 b 的长度。

    第二行三个整数 x,k,y(1≤x,y≤109,1≤k≤n) ——火球术消耗的法力值，火球术的范围和狂暴术消耗的法力值。

    第三行 n 个整数 a1,a2,…,an(1≤ai≤n)。保证 ai 是两两不同的。

    第四行 m 个整数 b1,b2,…,bm(1≤bi≤n)。保证 bi 是两两不同的。

    输出格式

    一行一个整数，即将序列从 a1,a2,⋯,an 变为 b1,b2,⋯,bm所需的最少法力值。如果无法完成变换，则输出−1。

Berserk And Fireball

Created by LXC on Tue Apr 9 14:16:55 2024

https://codeforces.com/problemset/problem/1380/D

ranting: 2000

tag: constructive algorithms, greedy, implementation, math, two pointers

problem

有 n 个战士站成一排，第 i 个战士的战力是 ai。所有战士的战力都是两两不同的。

你可以使用两种类型的咒语：

  1. 火球术：你可以消耗 x 点法力值来干掉连续的 k 个战士（你必须干掉正好 k 个，而不能干掉 ≤k 个）。

  2. 狂暴术：你可以消耗 y 点法力值，选择站在一起的两个战士使他们展开决斗，战力较弱的那个战士将会被干掉。

我们来举个例子，假设有 7 个战士，其战力分别为 [2,3,7,8,11,5,4]，且此时的k=3（k 的定义详见火球术）。如果你对战力为 8 与 11 的两个战士施加狂暴术，剩下战士的战力将会变成 [2,3,7,11,5,4]（战力为 8 的战士在决斗中战死）。然后如果我们对战力为 [7,11,5] 的战士施加火球术，剩下战士的战力将会变成 [2,3,4]。

你想要组建一支军队，因此你想要将所有战士战力的序列从 a1,a2,⋯,an 变为 b1,b2,⋯,bm。试计算你所需的最少法力值。

输入格式

第一行两个整数 n,m(1≤n,m≤2⋅105) ——序列 a 的长度和序列 b 的长度。

第二行三个整数 x,k,y(1≤x,y≤109,1≤k≤n) ——火球术消耗的法力值，火球术的范围和狂暴术消耗的法力值。

第三行 n 个整数 a1,a2,…,an(1≤ai≤n)。保证 ai 是两两不同的。

第四行 m 个整数 b1,b2,…,bm(1≤bi≤n)。保证 bi 是两两不同的。

输出格式

一行一个整数，即将序列从 a1,a2,⋯,an 变为 b1,b2,⋯,bm所需的最少法力值。如果无法完成变换，则输出−1。

solution

我们可以按照b在a数组中的元素作为分割点，将a分为若干段，对于bi和bi+1之间的a数组中的元素。如果最大元素大于bi,bi+1，那么至少需要一次火球术。之后，考虑一次火球术和k次狂暴的价格，优先选择价格低者。

code

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    ll n, m;
    cin >> n >> m;
    ll x, k, y;
    cin >> x >> k >> y;
    vector<ll> a(n), b(m+2, 0);
    for (auto& i:a) cin >> i;
    for (int i=1; i<=m; i++) {
        cin >> b[i];
    }
    ll p = 0;
    ll ans = 0;
    for (int i=1; i<=m+1; i++) {
        ll ca = 0, cm = 0;
        while (p<n && a[p] != b[i]) {
            ca++;
            cm = max(cm, a[p]);
            p++;
        }
        if (p == n && i<m) {
            cout << "-1\n";
            return ;
        }
        if (cm > max(b[i], b[i-1])) {
            if (ca < k) {
                cout << "-1\n";
                return ;
            }
            ans += x;
            ca -= k;
        }
        ans += ca/k*min(x, k*y)+ca%k*y;
        p = min(n, p+1);
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}