CF18B/01背包

B. Checkout Assistant

有 n n n件商品，每件需要花费 t i t_i ti​秒时间、 c i c_i ci​元钱支付。但是每一秒钟，你可以偷走一件商品（不用付钱），求最小支付金额。

如果购买了物品 i i i，相当于花费 c i c_i ci​元，拿走 t i + 1 t_i+1 ti​+1件物品，求拿走至少 n n n件物品的最小花费。

难点在于将问题转化为01背包模型，将01背包改改即可。

#include 
using namespace std;

const int N = 2e3 + 5;

int t[N], c[N];

int n, m;
long long dp[N];
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> t[i] >> c[i];
    memset(dp, 0x3f3f3f3f3f3f3f3f, sizeof dp);
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = n; j >= 1; j--)
            dp[j] = min(dp[max(0, j - t[i] - 1)] + c[i], dp[j]);
    cout << dp[n] << endl;
}

int main()
{
    solve();
    return 0;
}