厉害，背包还可以记忆化搜索
by YZhe @ 2019-05-10 21:55:52
@[_KaQqi](/space/show?uid=68055) 它只是道橙题，不要这么对它
by wwlw @ 2019-05-10 22:02:07
@[Tryer](/space/show?uid=117655) 难道不行吗QwQ
by _KaQqi @ 2019-05-11 08:27:22
记忆化
------------
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
using namespace std;
int ans[1001][1001],n,T;
int a[1001],v[1001];
int dfs(int x,int left_t)
{
if(ans[x][left_t]!=-1) return ans[x][left_t];
if(x==1+n) return ans[x][left_t]=0;
int sum1=-1,sum2=-1;
sum1=dfs(x+1,left_t);
if(a[x]<=left_t)
{
sum2=dfs(x+1,left_t-a[x])+v[x];
}
return ans[x][left_t]=max(sum1,sum2);
}
int main()
{
cin>>T>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i]>>v[i];
}
memset(ans,-1,sizeof(ans));
cout<<dfs(1,T);
return 0;
}
```
by PAN_盼达明 @ 2019-06-12 16:23:45
@[YZhe](/space/show?uid=117655) ？dp不就是记忆化搜索吗
by dbxxx @ 2019-10-04 14:04:27
@[东北小蟹蟹](/space/show?uid=120868) 记忆化搜索不就是dp吗
by YZhe @ 2019-10-04 14:29:01
@[YZhe](/space/show?uid=117655) ？所以背包用记忆化搜索怎么了吗`qwq`
by dbxxx @ 2019-10-04 14:31:39
@[东北小蟹蟹](/space/show?uid=120868) 我不会写的问题
by YZhe @ 2019-10-04 14:50:07