一种不太稳定的做法

二位大佬讲述了map优化超大背包的正解，那我就来说一下我是怎么用不太正确的复杂度卡进正解的吧。

实际上就是记忆化搜索……

然后开了n个unordered_map，就这样简简单单的通过了哈哈哈哈哈……

这道题的数据有待加强，毕竟这种剪枝做法真的不好说能不能通过。

AC代码：

#include <bits/stdc++.h>
using namespace std ;
#define int long long
int t[110] , v[110] ;
unordered_map<int,int> mp[110] ;


int dfs(int i, int j) {
    if(i==0)    return 0 ;
    if(mp[i-1].find(j)!=mp[i-1].end())    return mp[i-1][j] ;
    int res = dfs(i-1,j) ;
    if(j>=t[i])    res = max(res, dfs(i-1,j-t[i])+v[i]) ;
    return mp[i][j] = res ;
}

signed main() {
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) , cout.tie(nullptr) ;
    int n , S ;    cin >> n >> S ;
    for(int i=1 ; i<=n ; i++)    cin >> t[i] >> v[i] ;
    cout << dfs(n,S) << endl ;
    return 0 ;
}