洛谷 P1616 疯狂的采药 C语言 记忆化搜索

题目：

https://www.luogu.com.cn/problem/P1616?contestId=215526

完全背包问题，最后一个超出空间了。完全背包和就是无限次的拿，公式跟01背包差不多。

但是，只有当前能拿和拿不下，换下一个。注意要处理好边界条件。这里记忆化数组【第x个物品】【剩余时间有多少】= 储存的是拥有的价值。

#include <iostream>
using namespace std;
int T,M;
typedef long long ll;ll times[200000];
ll value[200000];
ll mem[20000][10000];
ll dfs(ll x,ll SPT)
{ll sum = 0;if(mem[x][SPT])return mem[x][SPT];if(x > M)return 0;else if (SPT < times[x]){sum = dfs(x+1,SPT);}elsesum = max(dfs(x+1,SPT),dfs(x,SPT - times[x]) + value[x]);//这里有差异mem[x][SPT] = sum;return sum;} 
int main(void) {cin >> T >> M;for(ll i = 1 ; i <= M ; i++)cin >> times[i] >> value[i];ll ans = dfs(1,T);cout << ans;return 0;
}