题目描述

难度分:$1600$

输入$n(2 \leq n \leq 500)$，$m(1 \leq m \leq 1000)$，长为$n$的数组$w(1 \leq a[i] \leq 100)$，长为$m$的数组$b(1 \leq b[i] \leq n)$。

0x3F有$n$本书，第$i$本书的重量为$w[i]$。这$n$本书按照某种顺序，从上到下摆成一摞。

有$m$天。在第$i$天，0x3F会阅读第$b[i]$本书。操作如下：

1. 阅读之前，0x3F需要把在$b[i]$上面的书抬起来，拿出$b[i]$，然后放下抬起来的书。这个过程会消耗一些体力，消耗值等于$b[i]$上面所有书的重量之和（不含$b[i]$）。
2. 阅读第$b[i]$本书。
3. 阅读之后，0x3F会把$b[i]$放在这摞书的最上面。

0x3F可以决定这$n$本书的初始摆放顺序。输出0x3F体力消耗之和的最小值。

输入样例

3 5
1 2 3
1 3 2 3 1

输出样例

12

算法

贪心+模拟

这个题在做的时候比较迷糊，感觉书的顺序是这样确定的：顺序遍历$b$，如果$b[i]$没有在前面出现过，就把$b[i]$追加到一个数组$bookPile$中，直到所有要阅读的书都出现过。此时$bookPile$从前往后就是书堆从上往下的顺序。

此摆放顺序消耗体力最少的结论我并没有严格证明，可以这么来思考：首先$n$本书中不存在于$b$数组中的书全部压底下就好了，什么顺序无所谓。由于之前读过的书都会放在最上面，所以我们尽量保证在阅读到$b[i]$时，它的上方只有$b$的前缀$[1,i)$中的书，因此按照这个构造方法可以得到一个最优解。

有了书堆中书本的摆放顺序就好做了，本题的$n$和$m$规模都比较小，直接模拟这个过程就行，详见代码实现。

复杂度分析

时间复杂度

得到初始书堆需要先遍历一遍$b$，时间复杂度为$O(m)$。模拟也需要遍历$b$，时间复杂度为$m$，对于每个$b[i]$，需要更新书堆数组$bookPile$，它的规模是$O(n)$级别的，所以动态更新它也是$O(n)$的时间复杂度（先$O(n)$找到$b[i]$，然后再将其从$bookPile$中移除添加到顶部，时间复杂度也是$O(n)$）。因此，算法整体的时间复杂度为$O(nm)$。

空间复杂度

空间消耗的瓶颈主要在于$bookPile$数组，而每次模拟更新它时也需要一个额外空间$top$来存储本轮需要重新调整顺序的书本编号（$b[i]$以及压在它上面的书本编号），两者都是$O(n)$级别的。因此，算法整体的额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#include <vector>

using namespace std;
const int N = 1010;
int n, m, w[N], b[N];

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
    }
    vector<int> book_pile;;
    unordered_set<int> st;
    for(int i = 1; i <= m; i++) {
        scanf("%d", &b[i]);
        if(st.find(b[i]) == st.end()) {
            st.insert(b[i]);
            book_pile.push_back(b[i]);
        }
    }
    reverse(book_pile.begin(), book_pile.end());
    int ans = 0;
    for(int index = 1; index <= m; index++) {
        // 搬上面的书
        vector<int> top;
        int j;
        for(int i = book_pile.size() - 1; i >= 0; i--) {
            if(book_pile[i] != b[index]) {
                ans += w[book_pile[i]];
            }else {
                j = i;
                break;
            }
        }
        // 调整一下书堆
        for(int i = book_pile.size() - 1; i > j; i--) {
            top.push_back(book_pile.back());
            book_pile.pop_back();
        }
        book_pile.pop_back();
        reverse(top.begin(), top.end());
        top.push_back(b[index]);
        for(int item: top) book_pile.push_back(item);
    }
    printf("%d\n", ans);
    return 0;
}