poj 3249 Test for Job (拓扑排序+dp)

http://poj.org/problem?id=3249

题意:

给一个DAG,现要从一条入度为0的点到一个出度为0的点,问最大点权和。

思路:

其实比较容易想到搜…不过复杂度会炸?

由于到一个点的最大点权和,需要更新完所有到达它的路线之后才能确定。

容易联想到拓扑排序,我们可以[……]

Read more

(dp专题006)hdu 2602 Bone Collector(01背包)

题目链接

题意:容量为V的背包,n个骨头,给出价值和体积,问最多能装多少价值的背包。

思路:01背包裸体。

 

[dp专题005]hdu 1864最大报销额(01背包,垃圾题)

hdu1864题目链接

题意:中文题目,不多说了。

思路:正解是01背包,呵呵呵。

出题人是傻逼吗?

不给数据范围?

以及,正解的01背包基于所有的发票额度的只有2位小数。这是让人猜?

本来看到这题这么恶心时不打算写的…

写了的原因纯粹是为了吐槽傻逼出题[……]

Read more

(dp专题004)hdu 2955Robberies(01背包变形)

题目链接

题意: 给出n个银行 ,以及抢劫每个银行可以得到的价值和被抓的概率,不同银行之间被抓的概率是相互独立的,现在给出安全概率p,只有当概率从小于安全概率时才是安全的,问最多能抢劫多少价值。

思路:一开始很直接就想到把概率算成容量,

于是就成了经典的01背包,然后发现概率是do[……]

Read more

【dp专题002】hdu 4489 The King’s Ups and Downs (dp)

题目链接

题意:问长度为n的“波浪”型排列(即1..n每个数出现一次)有多少。波浪型的含义是,“高低高”或者“低高低”

思路:我们考虑当前已经知道i-1个数的波浪型的排列的方案数,那么当第i个数到来时,第i个数一定是最大的。

那么将i插入到某个位置,必须满足该位置前面必须以“高低”[……]

Read more

[dp专题000]uva 10328 Coin Toss (java 大数+dp)(Unsolved)

题目链接

题意:问长度为n,每个位置由且仅有‘H’和’T’组成的序列中,至少有连续k个‘H’出现的方案数。

思路:不会做,参考了题解 不过没有完全搞懂。

根据题解,正面考虑比较麻烦,所以反面考虑。[j]

dp[i][j]表示长度为i,前面最后连续的‘H’的个数不超过j个的方案[……]

Read more