兀十三的星露谷冒险

wss114514 / 2024-07-20 / 原文

题面描述

最近，兀十三沉迷星露谷物语无法自拔。

在游戏中，她所操控的角色有两种属性：生命值H和能量值E，然而它们都是有上限的。她的物品栏中有n个可以分别恢复血量h和能量e的食物。现在假设当前生命值和能量值都为0，她想知道，自己至少要吃几个食物才能完全回满生命和能量（溢出上限的部分不计）？

输入格式

第一行输入 $H$ 和 $E$，表示生命值和能量值上限。

第二行输入一个整数 $n$，表示有 $n$ 个食物。

接下来 $n$ 行，每行输入2个整数 $h$ 和 $e$，分别表示该食物能够恢复的生命值和能量值。

输出格式

输出最少需要的食物数量。

若没有一种方案能够恢复满生命和能量，则输出“-1”。

数据范围

$1 \leq H, E \leq 10^{9}$
$1 \leq n \leq 20$
$-10^{9}\leq h, e \leq 10^9$

输入样例

10 10
2
5 6
7 5

输出样例

题解

数据范围启发可以使用指数级别的做法，用dfs对每个食物做一遍取或不取的操作，求得最少种类。

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

typedef long long ll;

const int N = 50;
ll H, E;
int res, n;
bool flag = 0;
struct food {
    ll h, e;
}f[N];

// 当前取到第i种食物，当前生命值为h，能量值为e，至少用了x种食物
void dfs(int i, ll h, ll e, int x) {
    if (i > n + 1) return;
    if (h >= H && e >= E) {
        flag = 1;
        res = min(res, x);
        return;
    }
    dfs(i + 1, h + f[i].h, e + f[i].e, x + 1); // 取
    dfs(i + 1, h, e, x); // 不取
}

int main() {
    cin >> H >> E;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> f[i].h >> f[i].e;
    res = 30;
    dfs(1, 0, 0, 0);
    if (flag) cout << res << "\n";
    else cout << "-1\n";
    return 0;
}