问题重述

Bob 有 $n$ 件商品，每件商品有两个属性：

• $t_i$：收银员处理这件商品所需的时间（秒）
• $c_i$：这件商品的价格

收银员一次只能处理一件商品，处理顺序由 Bob 决定。当收银员在处理某件商品时，Bob 可以偷走其他商品，偷一件恰好需要 $1$ 秒。

目标：最小化 Bob 实际支付的金额（即被收银员处理且未被偷走的商品的价格总和）。

关键点：

• 如果某件商品的 $t_i = 0$，则当收银员处理它时，Bob 无法偷任何东西（因为处理时间为 $0$，没有时间偷）。
• Bob 可以决定收银员处理商品的顺序。
• 被偷的商品不需要支付。

---

问题转化

假设 Bob 决定让收银员处理 $k$ 件商品（其余 $n - k$ 件被偷），设这些被处理商品的处理时间之和为 $S = \sum t_i$（只计算被处理的那 $k$ 件）。

偷窃时间约束：

• 在处理一件商品的过程中，Bob 可以偷其他商品，每偷一件需要 $1$ 秒。
• 因此，总偷窃时间上限 = 总处理时间 $S$（因为处理过程中 Bob 一直在偷）。
• 需要偷的商品数量 = $n - k$。

可行性条件：

$$S \ge n - k$$

即：

$$S + k \ge n$$

其中 $k$ 是被处理商品的数量，$S$ 是这些被处理商品的 $t_i$ 之和。

---

更直观的理解

我们换个角度：
每件商品要么被支付（即被收银员处理），要么被偷。

• 如果一件商品被支付，它贡献 $t_i$ 秒的偷窃时间，并花费 $c_i$ 元。
• 如果一件商品被偷，它需要消耗 $1$ 秒偷窃时间，花费 $0$ 元。

设 $T$ = 所有被支付商品的 $t_i$ 之和，$P$ = 所有被支付商品的数量。

约束：总偷窃时间 $T$ 必须 $\ge$ 被偷商品数量 $n - P$，即：

$$T \ge n - P \quad \Rightarrow \quad T + P \ge n$$

目标：最小化被支付商品的价格总和。

---

动态规划解法

这是一个 0/1 背包 变种。

状态定义

设 $dp[j]$ 表示：当被支付商品贡献的总时间 + 被支付商品的数量等于 $j$ 时，所需的最小支付金额。

即：

$$j = T + P$$

其中 $T$ 是被支付商品的 $t_i$ 之和，$P$ 是被支付商品的数量。

初始状态

$dp[0] = 0$，表示没有支付任何商品时，花费为 $0$。
其余 $dp[j] = \infty$。

状态转移

对每件商品 $(t_i, c_i)$，我们考虑是否支付它：

• 不支付（即偷走）：不改变 $T$ 和 $P$，不影响 $dp$。
• 支付：$T$ 增加 $t_i$，$P$ 增加 $1$，所以 $j$ 增加 $t_i + 1$，花费增加 $c_i$。

因此转移方程为：

$$dp[j + t_i + 1] = \min(dp[j + t_i + 1], dp[j] + c_i) $$

为什么是 $t_i + 1$？
因为每支付一件商品，它既贡献 $t_i$ 秒偷窃时间，又自身作为被支付商品计入 $P$，所以总“能力值” $j$ 增加了 $t_i + 1$。

答案

我们需要 $T + P \ge n$，即 $j \ge n$。
因此答案为：

$$\text{ans} = \min_{j = n}^{\text{max\_sum}} dp[j]$$

其中 $\text{max\_sum}$ 是 $j$ 可能的最大值。由于 $t_i \le 2000$，$n \le 2000$，最坏情况是支付所有商品：$j_{\max} = \sum t_i + n \le 2000 \times 2000 + 2000 = 4,002,000$，但实际我们只需取 $n + \max(t_i)$ 作为上界即可。

---

算法步骤

1. 读取 $n$ 和所有 $(t_i, c_i)$。
2. 设定 $M = n + 2000$（足够大的上界）。
3. 初始化 $dp$ 数组，$dp[0] = 0$，其余为 $\infty$。
4. 对每件商品，倒序遍历 $j$（0/1 背包防止重复使用），执行转移：$$dp[j + t_i + 1] = \min(dp[j + t_i + 1], dp[j] + c_i) $$
5. 最终答案为 $\min_{j = n}^{M} dp[j]$。
6. 输出答案。

---

标程代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF = 1e18;

int main() {
    int n;
    cin >> n;
    
    vector<int> t(n), c(n);
    int max_t = 0;
    for (int i = 0; i < n; i++) {
        cin >> t[i] >> c[i];
        max_t = max(max_t, t[i]);
    }
    
    // 最大可能的 j = n + max_t 足够（因为 T ≤ n * max_t 但我们只需考虑 j ≥ n）
    int max_sum = n + max_t;
    vector<ll> dp(max_sum + 1, INF);
    dp[0] = 0;
    
    for (int i = 0; i < n; i++) {
        // 倒序更新，确保每件商品只使用一次
        for (int j = max_sum; j >= 0; j--) {
            if (dp[j] != INF) {
                int nj = min(max_sum, j + t[i] + 1);
                dp[nj] = min(dp[nj], dp[j] + c[i]);
            }
        }
    }
    
    ll ans = INF;
    for (int j = n; j <= max_sum; j++) {
        ans = min(ans, dp[j]);
    }
    cout << ans << endl;
    
    return 0;
}

---

示例验证

示例 1

4
2 10
0 20
1 5
1 3

商品列表：

1. $(t=2, c=10)$
2. $(t=0, c=20)$
3. $(t=1, c=5)$
4. $(t=1, c=3)$

最优方案：支付商品 1、3、4，总时间 $T = 2 + 1 + 1 = 4$，支付数量 $P = 3$，$T + P = 7 \ge 4$，总花费 $10 + 5 + 3 = 8$。

示例 2

3
0 1
0 10
0 100

所有 $t_i = 0$，支付任何商品都不产生偷窃时间。
要满足 $T + P \ge n$，即 $0 + P \ge 3$，必须支付所有 $3$ 件，花费 $1 + 10 + 100 = 111$。

---

复杂度分析

• 时间复杂度：$O(n \cdot (n + \max t_i)) \approx 2000 \times 4000 = 8 \times 10^6$，完全可以接受。
• 空间复杂度：$O(n + \max t_i) \approx 4000$，很小。

---

总结

本题的关键在于将问题转化为 0/1 背包，并定义状态 $j = T + P$（总处理时间 + 支付商品数量）。
这样，可行性条件 $T + P \ge n$ 就变成了 $j \ge n$，非常简洁。
转移时每件商品贡献 $t_i + 1$ 到 $j$，花费 $c_i$，最后取 $\min_{j \ge n} dp[j]$ 即为答案。