题目描述
解题思路
每次操作需要将一个球拿出来然后放在最上面,观察一下,我们发现按照题目中给出的顺序排列即消耗体力最少,因为若在第一次操作的小球上面还有球,则在移动第一次操作的小球时,就会另加上最上面的小球的重量,同理在给出的序列的其他地方插入小球,也会使消耗体力增加。
顺序有了,模拟一下即可得出结果。
假设i,j为相同类型的小球,操作序列为。。。i。。。。j。。。,那么取j球时所花的体力为i的后一个球到j球的重量和;我们可以开一个数组,存该类型的球上一次出现的位置。
但是
还有一个坑点,从i到j遍历时,可能有一种类型的球出现了多次,但该球只能做一次贡献(o_ _)ノ
AC代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; int a[2010],b[2010],last[2010]; bool vis[2010]; //用vis数组记录该类型的球是否出现过 int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; ll ans=0; for(int i=1;i<=m;i++){ memset(vis,false,sizeof(vis)); cin>>b[i]; for(int j=last[b[i]]+1;j<i;j++){ if(vis[b[j]]==false){ vis[b[j]]=true; ans+=a[b[j]]; } } last[b[i]]=i; } cout<<ans<<endl; return 0; }