VOJ 扑克牌 题解 01背包dp

扑克牌

题目描述

给定一摞 n 张扑克牌，每张牌上有两个值 $a_i,b_i$，有以下两种操作：

1. 对于牌顶的牌 ($a_{top},b_{top}$) ，从上到下将把包括他在内的 $a_{top}$ 张牌扔掉并获得 $b_{top}$ 的愉悦度。注意：如果牌堆里面没有 $a_{top}$ 张牌的话不能进行此操作。
2. 把牌堆顶的牌扔到这摞牌的最下面。

现在你可以进行无限次操作，也可以在任意时刻停下来，问你最多能获得多少愉悦度。

输入格式

第一行一个数字 n, 接下来 n 行从上到下描述每张牌：每行两个数字表示牌上两个数字 $a_i,b_i$。

输出格式

一行一个数，表示最多的愉悦值。

样例

输入样例

3
2 3
1 2
1 1

输出样例

5

数据范围与约定

对于 $30\%$ 的数据，有 $n\le 5$。

对于 $100\%$ 的数据，有 $n\le 10^3,a_i\le n,b_i\le 10^3$。

思路

可以证明，在ai总和小于等于n时，总能找到一个扔牌顺序，使得扔选到的牌时不会扔到其他选到的牌。
因此，该问题即可转化为经典的01背包问题，其中ai为物品大小，bi为物品价值，n为背包容量。

原题

LOJ6217——传送门

代码

#include <bits/stdc++.h>
using namespace std;
#define max_Heap(x) priority_queue<x, vector<x>, less<x>>
#define min_Heap(x) priority_queue<x, vector<x>, greater<x>>
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
const double PI = acos(-1);
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n; // 背包容量
    cin >> n;
    vector<int> v(n + 1), w(n + 1), dp(n + 1);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i] >> w[i]; // 物品大小，物品价值
    }
    // 01背包dp
    for (int i = 0; i < n; i++)
    {
        for (int j = n; j >= v[i]; j--)
        {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    int ans = 0; // 最多愉悦值
    for (int i = n; i >= 0; i--)
    {
        ans = max(ans, dp[i]);
    }
    cout << ans << '\n';
    return 0;
}