4733: 【GESP2512六级】道具商店

题意分析

01 背包变形题。

• n 最多 500，每个道具攻击力\(a_i \le 500\)，总攻击力最大 = 500*500 = 250000
• 但是金币 k、花费\(c_i\)可以到\(10^9\)，不能把金币作为 dp 数组下标（普通 01 背包过不去）。

普通 01 背包：dp[cost]=max_val，这里反过来：

dp[x] = 获得x 点攻击力，需要花费的最少金币。

最后遍历所有攻击力 x，找到最大的 x 满足dp[x] ≤ k，就是答案。

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int MAXA = 500 * 500; // 250000

ll dp[250010];

int main()
{
    int n;
    ll k;
    cin >> n >> k;

    // dp初始化
    for(int i = 0; i <= MAXA; i++) dp[i] = INF;
    dp[0] = 0;

    for(int i = 1; i <= n; i++)
    {
        int a; ll c;
        cin >> a >> c;
        // 01背包倒序
        for(int j = MAXA; j >= a; j--)
        {
            if(dp[j - a] != INF)
            {
                dp[j] = min(dp[j], dp[j - a] + c);
            }
        }
    }

    // 找最大攻击力，花费<=k
    int ans = 0;
    for(int x = MAXA; x >= 0; x--)
    {
        if(dp[x] <= k)
        {
            ans = x;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 505;
const int oo = 1e9 + 10;
int n, k;
int f[N * N];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i < N * N; i++)
        f[i] = oo;
    int s = 0;
    for (int i = 1; i <= n; i++) {
        int a, c;
        scanf("%d%d", &a, &c);
        s += a;
        for (int j = s; j >= a; j--)
            f[j] = min(f[j], f[j - a] + c);
    }
    int ans = 0;
    for (int i = 0; i < N * N; i++)
        if (f[i] <= k)
            ans = i;
    printf("%d\n", ans);
    return 0;
}