从 hdu 3449 看一类最简单的依赖背包
发布时间:2020-12-13 19:43:10 所属栏目:百科 来源:网络整理
导读:此类背包典型的关系是若想选b,你必须先选a,从而产生了一层依赖关系,然后给你一定限量的总钱数,让你买最大价值的东西 就让我们从hdu 3449 来搞定这类最简单的依赖背包吧 有很多个箱子,想买箱子中的物品必须先买下箱子,典型的依赖背包 dp[i][j]代表前i个
此类背包典型的关系是若想选b,你必须先选a,从而产生了一层依赖关系,然后给你一定限量的总钱数,让你买最大价值的东西 就让我们从hdu 3449 来搞定这类最简单的依赖背包吧 有很多个箱子,想买箱子中的物品必须先买下箱子,典型的依赖背包 dp[i][j]代表前i个箱子花费j的钱能获得的最大价值,则可以想到每次在对一个箱子进行dp更新状态时都应该利用前面的结果来更新 以前做那道金明的预算方案时,就是没有利用上层的结果来更新才一直错,dp的本质都被我给忽略了,囧!
View Code
#include<cstdio> 也可以不用tmp数组
View Code
#include<cstdio> 还可以用一维的 dp[i]代表花i的钱能得到的最大价值
View Code
#include<stdio.h> (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |