CCA的搬运

题目链接：nowcoder 217041

到主站看：https://blog.csdn.net/weixin_43346722/article/details/115219135

题目大意

一个洞中有 n 个质量的球，要进行一些操作，每次把一个求拿出来放到最上面。
拿的费用是它上面小球质量和。
给出每次要拿的小球的编号，问你找到一种初始球的位置方案，使得花费体力最小。

思路

首先我们考虑怎么让体力最小。

那既然每次会把球放到最上面，那我们就会发现，它上面至少会有的球是它上一次放到最上面到现在放到上面的球。
就比如序列是：，那第二次把 放上去的时候，它的前面就至少会有 。

那我们要让花费体力最小，就尽可能让它的前面除了这些东西不再有别的。
那构思就出来了，如果这个要上提的球之间没有见过，就把它放在现在一直序列的最后面，然后再提到最前面。
如果之前见过，那我们就把它提到最前面。

那如果一直没有见过，就把它们放在最最后面。（顺序无所谓，因为它们的后面都不会有要提上去的点，都不会对总费用产生贡献）

然后因为可以 ，那我们上移就直接模拟，一个一个的替换，往上跳就可以过了。

代码

#include<cstdio>
#include<algorithm>
#define ll long long 

using namespace std;

int n, m, a[2001], sum;
int xx[2001], now;
bool nd[2001];
ll ans;

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    for (int i = 1; i <= m; i++) {
        scanf("%d", &now);
        if (!nd[now]) {
            nd[now] = 1;
            ans += 1ll * sum;//把它放在最下面，那移动的费用就是上面所有球的质量和
            sum += a[now];
            xx[++xx[0]] = now;
            for (int j = xx[0] - 1; j >= 1; j--)//移到最上面
                swap(xx[j], xx[j + 1]);
        }
        else {
            for (int j = xx[0]; j >= 1; j--)
                if (xx[j] == now) {
                    for (int k = j - 1; k >= 1; k--) {//移到最上面
                        ans += 1ll * a[xx[k]];//统计移上去的费用
                        swap(xx[k], xx[k + 1]);
                    }

                    break;
                }
        }
    }

    printf("%lld", ans);

    return 0;
}