Posted on 2013-08-21 14:09
happyac 阅读(1683)
评论(0) 编辑 收藏 引用 所属分类:
poj
总结
动态规划问题
分析
目标是从$n$个人中选出$m$个人，使得：
- $|D-P|$最小
- 如果最小不唯一，选$D+P$最大一组
设$s[i][j][k]$保存从$i$个人中选$j$个人的所有状态，那么根据第$i$个人选不选即可列出状态转移方程。
陷阱
状态数组的維数是可以减少的，可以将每一维去掉，但是需要有额外的操作：
- 考虑第$i$个人选不选时，还需要考虑这个人是否已经被选择
- 要将结果按人的先后次序排序