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，選的話有間斷性，就不能這樣寫。