原题链接：Codeforces500C
一共有 $n$ 本书摞在一起，每本书的重量为 $w_i$ 。共有 $m$ 天，每天需要看的书编号为 $b_i$，要取出想看的书，必须要搬掉上面所有的书，代价为想看的书的上面所有书的重量之和（不包括自己），求通过合适的初始摆放顺序，能使得 $m$ 天看书的总代价最小。
贪心 + 模拟
贪心策略：书的初始摆放方式为，按照第一次读到该本书的顺序从上至下摆放。当然永远不会读的书就不用管了，垫在底下就行了。然后模拟看书过程即可，如果用栈维护，栈顶就是书堆的顶部，具体详见代码注释。
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
|
#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 1010;
int n, m;
int w[N], b[M];
int stk[N], t[N], top;
bool st[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> w[i];
for (int i = 1; i <= m; i++) cin >> b[i];
// 初始化书的位置
int k = 0;
for (int i = 1; i <= m; i++) {
if (!st[b[i]]) {
t[++k] = b[i];
st[b[i]] = true;
}
}
// 逆置入栈，栈顶为第一本书
for (int i = k; i; i--) stk[++top] = t[i];
// 模拟每天看书的过程
int res = 0;
for (int i = 1; i <= m; i++) {
int x = b[i];
// 从栈顶开始往下找x
k = 0;
int sum = 0; // 要取出x，需要搬掉的重量为sum
while (stk[top] != x) {
sum += w[stk[top]];
t[++k] = stk[top--];
}
top--; // 删掉x
// 将原来上面的书放回去
for (int j = k; j; j--) stk[++top] = t[j];
stk[++top] = x; // x放到顶部
res += sum;
}
cout << res << endl;
return 0;
}
|