教育技术学网站模版,国内最新消息新闻,建设厅网站的投诉可以哪里查,建设网站设计的公司题目#xff1a;
https://www.luogu.com.cn/problem/P1616?contestId215526
完全背包问题#xff0c;最后一个超出空间了。完全背包和就是无限次的拿#xff0c;公式跟01背包差不多。
但是#xff0c;只有当前能拿和拿不下#xff0c;换下一个。注意要处理好边界条件。…题目
https://www.luogu.com.cn/problem/P1616?contestId215526
完全背包问题最后一个超出空间了。完全背包和就是无限次的拿公式跟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(x1,SPT);}elsesum max(dfs(x1,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;
}
