2023牛客暑期多校训练营5 - Nazrin the Greeeeeedy Mouse

Solost

2023 年 08 月 02 日

129 次浏览

暂无评论

1772字数

题目题解

## 题目链接

[链接](https://ac.nowcoder.com/acm/contest/57359/H)

## 题目大意

有n个物品，m个背包（体积从小到大给出），每个物品都有体积和价值，问m个背包能装下物品的最大价值是多少

## 题解

//dp[i][r]代表前i个背包存前r个物品时候能最大价值

每增加一个背包，就可以算出能存放物品的最大价值

转移方式为dp[i][r] = max(dp[i][r] , dp[i-1][l] + f[l + 1][r][sz[i]])

//f[l, r, k]代表编号为l-r的物品能放进背包容量为k时物品的价值

这就相当于转移了n次的01背包

## 代码

```cpp
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define fp(i, a, b) for (int i = a, i##_ = b; i <= i##_; ++i)
#define fd(i, a, b) for (int i = a, i##_ = b; i >= i##_; --i)

using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
using ull = unsigned long long;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 210, M = 2e5 + 10;

ll n, m;
int a[N], b[N], sz[M];
int f[N][N][N], dp[N][N];

void init() {
    fp(l, 1, n) {
        fp(r, l, n) {
            fp(k, 1, 200) {
                f[l][r][k] = f[l][r - 1][k];
                if (k >= a[r])
                    f[l][r][k] = max(f[l][r][k], f[l][r - 1][k - a[r]] + b[r]);
            }
        }
    }
}

void solve() {
    cin >> n >> m;
    fp(i, 1, n) {
        cin >> a[i] >> b[i];
    }
    fp(i, 1, m) {
        cin >> sz[i];
    }
    int st = max(1ll, m - n);
    init();
    fp(i, st, m) {
        fp(r, 0, n) {
            fp(l, 0, r) {
                dp[i - st + 1][r] = max(dp[i - st + 1][r], dp[i - st][l] + f[l + 1][r][sz[i]]);
            }
        }
    }
    cout << dp[m - st + 1][n] << endl;;
}
int main() {
    // IOS;
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 08 月 02 日