Hdu/Hdoj 2048 数塔

2009-04-29 15:48:24

Accepted

2084

15MS

300K

440 B

C++

Master Jedi

对于问题“从第i层第j个结点出发 如何向下走到底层 使所经过的权值最大”，有2个选择：走左边 和 走右边。
做出1个选择：假设选择走左边结点k，然后再按一定路线（不必考虑具体路线，假设已知）走到底层，可以得到最优解。
那么随之发生的子问题是：“从左结点k出发 如何向下走到底层 使所经过的权值最大”。
用反证法容易证明：从第i层第j个结点出发 向下走到底层的最优路线，包含了从左结点k出发向下走到底层的最优路线。该问题具有最优子结构性质。
而子问题“从第i层第j个结点出发 如何向下走到底层 使所经过的权值最大”很明显具有重叠性。
于是自底向上DP即可解决问题。
f[i][j]：表示从第i层第j个结点出发向下走到底层能够得到的最大权值。
状态转移方程：f[i][j]=MAX(f[i+1][j],f[i+1][j+1]);

Hdu/Hdoj 2670 Girl Love Value

2009-04-27 13:44:16

Accepted

2670

125MS

4204K

870 B

C++

Master Jedi

把问题分为两个子问题：
1.选出哪k个boy；
2.按什么顺序选。
每个boy有两个属性：喜欢度 和 衰减速度。
其中衰减速度是关键。
我的感觉是：最好先选择衰减速度快的人（貌似贪心），好让总的衰减值最小。
因此先按衰减速度递减排序（解决子问题2），再DP（解决子问题1）。
其中f[i][j]表示：从前i个人中 按一定次序选出j个人 得到的最优喜欢度。