问题描述
暑假到了，
Rick
制定了一个长达
M
天的阅读计划。他一共有
N
本书，从
1
至
N
进行标号；
Rick
将它们从上至下摞成一堆。他每天都会读一本书，假设他要读编号为
X
的书，他会按照以下步骤：
1.
将这本书上方的所有书搬起来
2.
将这本书拿出来
3.
将搬起来的书摞回去
4.
看完后把这本书放到顶端
每本书都会有各自的重量，
Rick
不希望搬起太过重的书。于是他希望能重新安排这
N
本书的顺序，使得读完
M
本书之后，搬书的重量之和最小。
输入格式
(
book.in
)
第一行两个整数
N
与
M
，分别代表书的数量和阅读的天数。
第二行
N
个整数，代表每本书的重量。
第三行
M
个整数，代表每天要读的书的编号。
输出格式
(
book.out
)
一行一个整数，代表最小的重量之和。
样例输入
3 5
1 2 3
1 3 2 3 1
样例输出
12
样例解释
DAY1
：
1 3 2
–
搬起重量
= 0
DAY2
：
1 3 2
–
搬起重量
= 1
DAY3
：
3 1 2
–
搬起重量
= 4
DAY4
：
2 3 1
–
搬起重量
= 2
DAY5
：
3 2 1
–
搬起重量
= 5
总和
= 0 + 1 + 4 + 2 + 5 = 12
数据范围与约束
对于
30%
的数据，
N
<=10.
对于
100%
的数据，
2<=N<=500, 1<=M<=1000,
每本书重量不超过
100.
思路：
贪心，先读到的放在上边，最后模拟那个过程，把重量加起来。
#include<iostream> #include<queue> #include<math.h> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,w[600]; int q[1200],cnt,last[600],f[1200]; int vis[600]; int ans,tot; int main() { freopen("book.in","r",stdin);freopen("book.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1,c;i<=m;i++) scanf("%d",&q[++cnt]); for(int i=1;i<=m;i++) { if(!last[q[i]]) ans+=tot,tot+=w[q[i]],last[q[i]]=i; else{ int t=last[q[i]]+1; memset(vis,0,sizeof(vis)); for(t;t<i;t++) if(!vis[q[t]]) ans+=w[q[t]],vis[q[t]]=1; last[q[i]]=i; } } cout<<ans; return 0; }