题目描述

blablabla

样例

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <vector>
#include <functional> //lambda递归
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define lb long double
#define endl '\n'
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const ll inf = 1e18;
// int d[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};//  上右下左

void solve()
{
    int t, m;
    cin >> t >> m;
    vector<int> vol(m + 1), val(m + 1);
    for (int i = 1; i <= m; i++)
    {
        cin >> vol[i] >> val[i];
    }
    vector<int> dp(t + 1);
    for (int i = 1; i <= m; i++)
    {
        for (int j = t; j >= vol[i]; j--)
        {
            dp[j] = max(dp[j], dp[j - vol[i]] + val[i]);
        }
    }
    cout << dp[t];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int _ = 1;

    // cin >> _;
    while (_--)
    {
        solve();
    }
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla