题解

交换不会增加糖果数量，但能改变种类。所以便宜商店不一定只买一颗：多买的糖果可以留到后面交换。

真正需要留意的是：一种糖果最后一次出现时，如果还没有留下它，以后就再也拿不到了。

设一共有 $D$ 种糖果，$last[x]$ 表示种类 $x$ 最后出现的位置。

算法 0：直接记录手里的糖果

$n\le 8$ 时，可以直接按题意做。将出现的种类重新编号，用一个数组记录每种糖果的数量。

依次经过商店，对当前每一种状态尝试：不操作、购买，以及交出一种当前持有的不同种类的糖果。交换时只需枚举交出哪一种，不必区分同种类的不同糖果。相同状态只保留花费最少的方案。

处理完所有商店，在每种糖果数量都大于零的状态中取最小花费。每个合法方案都对应其中一条转移路径，因此不会遗漏。

任何时刻持有的糖果总数不超过 $n$，状态数至多为 $\binom{n+D}{D}$。若用长度为 $D$ 的数组作为哈希键，按数组复制和哈希的开销计，期望时间为 $O(nD^2\binom{n+D}{D})$，空间为 $O(D\binom{n+D}{D})$。这只是一个宽松上界，$n\le8$ 时足够使用。

预期通过子任务 1，获得 15 分。

先把“能不能换到”说清楚

假设已经决定在哪些商店购买。记经过前 $i$ 家商店时，已经到达最后一次出现位置的种类数为 $b_i$。

这些种类以后都买不到、也换不到了，必须每种至少留一颗。因此，前 $i$ 家商店中选择购买的次数，必须至少为 $b_i$。

这个条件不仅必要，而且足够。可以这样安排交换：

• 买到的糖果先拿在手里，不急着交换。
• 走到某一种糖果的最后一家商店时，如果手中已有这种糖果，就留下一颗，以后不再拿它交换。
• 如果没有，就拿一颗尚未被留下的糖果换成这种糖果，再将它留下。

为什么最后一步总有糖果可换？设这是第 $r$ 个到达最后出现位置的种类。此时至少已经买了 $r$ 颗，之前只需要固定留下 $r-1$ 颗，因此一定还剩一颗可用。既然手里没有当前种类，交出的糖果也一定是不同种类。

如果当前位置本身被选为购买位置，那么买到的正是当前种类，直接留下一颗即可，不会出现同一家商店既买又换的情况。

所以问题变成了：选一些购买位置，使每个前缀中的购买次数至少为 $b_i$，并让总价格最小。

最终只需要买 $D$ 颗。若一个满足条件的方案买了超过 $D$ 颗，删掉其中最靠后的购买位置：它之前的前缀不受影响，它之后仍至少买了 $D$ 颗，也就不会违反任何前缀要求。重复删到 $D$ 颗，费用不会增加，因为价格非负。

算法 1：价格单调不降

至少需要买 $D$ 颗，而前 $D$ 家商店恰好是最便宜的 $D$ 家。因此，下界是前 $D$ 个价格之和。

在前 $D$ 家商店全部购买，之后只交换或跳过，这个下界能够达到。因为前 $i$ 家商店中买了 $\min(i,D)$ 颗，而 $b_i\le i$ 且 $b_i\le D$，满足前面证明的条件。

统计不同种类的数量，再求前 $D$ 个价格的和即可。用数组标记种类，时间和空间均为 $O(n)$。

预期通过子任务 2，获得 20 分。结合算法 0 可以获得 35 分。

算法 2：只记录买了多少颗

现在不用记录每种糖果的数量了，只要检查每个前缀的购买次数。

令 $dp_{i,j}$ 表示经过前 $i$ 家商店、恰好买了 $j$ 颗糖果，并且已经满足所有前缀要求时的最小花费。初始 $dp_{0,0}=0$，其余状态不可行。

第 $i$ 家商店有买与不买两种选择：

$$dp_{i,j}=\min(dp_{i-1,j},dp_{i-1,j-1}+c_i).$$

计算后，将所有 $j<b_i$ 的状态设为不可行。答案为 $dp_{n,D}$。

这里“不买”不代表一定跳过，也可以进行交换；交换是否可行已经由前缀条件保证，不需要再写进状态。转移枚举了所有购买位置的选择，删除的也恰好是不能满足前缀要求的方案。

时间复杂度 $O(n^2)$。将 $j$ 从大到小更新，可以滚动成一维，空间复杂度 $O(n)$。

预期通过子任务 1、3，获得 40 分。再对价格单调不降的情况单独处理，可以获得 60 分。

算法 3：到最后一次出现时，再选一个最便宜的购买位置

按顺序扫描商店，将经过的价格放进小根堆。

如果第 $i$ 家商店不是当前种类的最后一家，暂时不必做决定。如果 $i=last[a_i]$，就多了一个必须留下的种类，需要再确定一次购买：取出堆里最便宜的价格，加入答案。

堆里存的是“前面还没有被选中的购买位置”，并不是当前拿着的糖果。取到早先某家店的价格，表示规划方案时决定在当时购买，不是走回去购买。

为什么可以每次只拿最便宜的？将各类糖果的最后出现位置从小到大排列，设当前处理第 $r$ 个位置。之前已经固定了 $r-1$ 次购买。

考虑一个包含这些已固定购买位置的最优方案。它在当前位置之前至少买了 $r$ 次，所以一定还有一个未固定的购买位置 $p$。设堆里最便宜的位置是 $q$。如果最优方案还没有选择 $q$，就用 $q$ 替换 $p$：

• 费用不会增加，因为 $c_q\le c_p$。
• 之前各次截止的要求，由已经固定的 $r-1$ 次购买保证，不受影响。
• 当前及之后的截止位置，都在 $p,q$ 后面，替换不改变这些前缀中的购买次数。

因此，每次贪心都可以让某个最优方案包含新选的位置。处理完 $D$ 次截止，就得到了最优的 $D$ 次购买。

每个价格入堆一次，至多出堆一次，时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。答案可能达到 $2\times10^{14}$，需要使用 long long。

预期通过所有子任务，获得 100 分。

参考代码

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int a[N], c[N], last[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> c[i];
        last[a[i]] = i;
    }
    priority_queue<int, vector<int>, greater<int> > q;
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        q.push(c[i]);
        if (last[a[i]] == i) {
            ans += q.top();
            q.pop();
        }
    }
    cout << ans << "\n";
    return 0;
}