原题
题目大意
该题的背景是读书, 书是叠起来的一堆, 如果要读的书是在下面的话, 则需要把这本书上方的书堆先搬走, 把这本书拿出来, 再把书堆搬回去, 读完后的书放在书堆顶部. 题目给出多少本书以及每本书的重量, 还有要读的书 (按先后顺序给出), 同一本书可能被读多次. 书堆刚开始的堆叠顺序是未知的 (由你安排), 要求所有要读的书读完后总共需要搬的书的重量之和最少, 并输出该值.
题目分析
通过模拟这个过程可以发现一些性质, 就拿题目样例来说, 书单是 1 3 2 3 1, 第 i 本书的重量是 i. 从左往右看书单, 首先现在假设现在书堆是空的, ans=0(所需要搬的书的重量和), 我们一本一本把书加进去. 首先是 1, 就把第 1 本书加入这个书堆, 不需要搬书. 第二个是 3, 把它放入书堆顶, 需要先搬走第一本书, ans+=1. 第三个是 2, 同理放到堆顶, ans+=3+1. 第四个是 3,3 在书堆里已经存在了, 那只需要找在它上面的书, 把重量加起来即可, 即 ans+=2. 最后一个是 1, 同理 ans+=3+2. 现在说一下怎么实现这个过程. 首先需要一个 max, 用来记录进入新书时该搬多少重量的书的, 然后如果不是新书的话就往前搜索, 直到搜索到同样的书为止, 也就是记录这本书上面有多少本书.
代码
- #include <cstdio>
- #include <cmath>
- #include <iostream>
- #include <cstring>
- #include <algorithm>
- #include <vector>
- #include <string>
- #include <utility>
- #include <queue>
- #include <stack>
- const int INF=0x3f3f3f3f;
- using namespace std;
- int w[501],b[1001];
- int sign[501];
- int s[501];
- int find(int x)
- {
- int sum=0;
- for(int i=x-1;b[i]!=b[x];i--)
- if(!s[b[i]]) sum+=w[b[i]],s[b[i]]=1;
- memset(s,0,sizeof(s));
- return sum;
- }
- int main()
- {
- int n,m;
- cin>>n>>m;
- for(int i=1;i<=n;i++) cin>>w[i];
- for(int i=1;i<=m;i++) cin>>b[i];
- int ans=0,max=0;
- for(int i=1;i<=m;i++)
- {
- if(!sign[b[i]]) ans+=max,sign[b[i]]=1,max+=w[b[i]];
- else ans+=find(i);
- }
- cout<<ans<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2971637.html