[CF1154F] Shovels Shop - dp

Description

商店里有 \(n\) 双鞋，你要买其中的严格 \(k\le 5000\) 双。你每次购买可以挑选剩余鞋中的任意一个子集来购买集合中所有的鞋。有 \(m\) 种套餐，第 \(i\) 种套餐代表如果一次性购买 \(x_i\) 双鞋则其中最便宜的 \(y_i\) 双免费。这 \(m\) 种套餐每种都可以用任意次。现在请求出买严格 \(k\) 双鞋的最小化费。

Solution

显然我们只会买最便宜的 \(k\) 双，因此可以设计一个 \(n^2\) 的 dp，对排序后的，\(f[i]\) 表示买前 \(i\) 件需要的最小花费，预处理 \(h_i\) 表示买 \(i\) 双最多能免单多少双

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

#define int long long

const int N = 2005;

int f[N], h[N], s[N], a[N * 100], n, m, k;

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= k; i++)
        s[i] = s[i - 1] + a[i];
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        if (x > k)
            continue;
        h[x] = max(h[x], y);
    }
    for (int i = 1; i <= k; i++)
        h[i] = max(h[i], h[i - 1]);
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for (int i = 1; i <= k; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            f[i] = min(f[i], f[i - j] + s[i] - s[i - j + h[j]]);
        }
    }
    cout << f[k] << endl;
}