1243专题

poj 1243 One Person(dp,记忆化搜索)

题目大意: 有一个人在猜数字,总共有G次猜测机会,L次猜高的机会。问他能够猜对的最大数字是什么。 如果猜错,那么G-1,如果是猜高了,那么需要额外L-1,当猜对或者G<0或者L<0的时候,猜测结束。 一开始把题目理解成:猜低,G-1,猜高L-1,G变为初始值。但是样例都不过掉。 解题思路: 根据正确的题意,那么我们可以很容易想到一个状态转移方程:dp[i][j] = dp[i-1]

vijos 1243 生产产品 单调性优化动态规划

描述 Description 在经过一段时间的经营后,dd_engi的OI商店不满足于从别的供货商那里购买产品放上货架,而要开始自己生产产品了!产品的生产需要M个步骤,每一个步骤都可以在N台机器中的任何一台完成,但生产的步骤必须严格按顺序执行。由于这N台机器的性能不同,它们完成每一个步骤的所需时间也不同。机器i完成第j个步骤的时间为T[i,j]。把半成品从一台机器上搬到另一台机器上也需要一定的时