POJ - 1018 Communication System题解

题目大意：

给定N组通信设备，并在每组之后输入多个相关的零件制造商给出的可建造带宽数和相应价格。每组只能选择一个零件制造商，并规定B为选出来的N个制造商中宽带最小的数值。SumP是N个选出来的制造商价格之和。要求最终B/SumP的最大值，并且保留三位小数输出。

思路：

首先决策比较容易分析（通常来讲），比如此题中，每组只能选一个，每组的制造商只有选或着不选两种状态。由于动态规划需要包含所有状态。设状态式为dp[i][b]表示在前i组零件中以B为最小值时的SumP。

dp[i][k]=min(dp[i][k],dp[i-1][k]+price[i][j]) ：{这里表示价格要求最小值}

注意一下这里的状态转移形式，这种形式是线性dp的模板类型，同类型的还有最大子序列和，这种dp问题有严格的连续性，但是比如最长上升子序列，1，3， 2， 4，5，选的话有间断性，就不能这样写。