题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1069
题目大意：


	题意分析：
	  题目本身描述得比较绕口，这里利用题目给的测试用例的输入描述一下：
	              生产的   厂家m1     厂家m2    厂家m3
	              厂家数   B1   P1    B2  P2    B3 P3
	  路由设备n1：  3     [100 25]   [150 35]  [80 25]
	  路由设备n2：  2     [120 80]   [155 40]
	  路由设备n3：  2     [100 100]  [120 110]
	  
	  简单而言，有n种通讯设备（在本题中可类比成网络路由器），
	  每种路由器最少有1个厂家、最多可以有m个厂家负责生产，
	  当然，不同的厂家生产的路由器性价比都是不一样的，
	  而影响路由器性价比的取决于其 带宽B 和 价格P
	  现在某通讯公司要采购n个路由器集成为一个网络系统，
	  每个路由器可以从不同的厂家中采购。
	  由于带宽存在短板效应，这个网络系统的最大带宽 sysB 取决于这n个路由中最小的带宽
	  
	  而这个网络系统的价格 sysP 等于这n个路由的价格之和
	  问以最好的性价比为目标去选购n个路由组装网络系统，
	  这个性价比的值 sysB/sysP 是多少 ?
	  
	解题思路：
	  首先需要简化状态。
	    题目要求的最终状态性价比是由 带宽和价格 两个变量影响的，不易构造DP的状态转移方程。
		为此可将问题状态转化为以下问题集：
		【求在[各种带宽]的情况下组装网络系统的[最小价格]】
		
令 dp[e][B] 表示选择[前e个]路由设备所构成带宽为B的系统所需支付的最小价格，
	 注意B是离散的，且因为短板效应受[前e-1个]路由设备构成的带宽影响
	 那么状态转移方程为：
	   for(int i=1;i<=n;i++)
       {
           for(int j=1;j<=m[i];j++)
           {
               int B=b[i][j];//设备i被厂家j生产时的带宽B
               int P=p[i][j];//设备i被厂家j生产时的价格P
               if(i==1)
               {
                   dp[1][B]=min(dp[1][B], P);
               }
               else
               {
                   for(int k=1;k<B;k++)//最小带宽发生改变
                   {
                       if(dp[i-1][k]<inf)//前状态存在
                       {
                           dp[i][k]=min(dp[i][k], dp[i-1][k]+P);
                       }
                   }
                   for(int k=B;k<500;k++)//最小带宽不发生改变
                   {
                       if(dp[i-1][k]<inf)//前状态存在
                       {
                           dp[i][B]=min(dp[i][B], dp[i-1][k]+P);
                       }
                   }
               }
           }
       }

思考：暑假也做过dp记录状态的题，还是没有搞的太明白
全部代码：

#include <iostream>
#include <stdio.h>

using namespace std;
#define LL long long
#define p1 first
#define p2 second
//memset(a, 0, sizeof(a));
//stack堆栈 queue队列 priority_queue优先队列
//vector向量 multiset平衡二叉树 deque双端队列
//pair{T1 first;T2 second;} greater<T>
//unordered_map 哈希map
const int inf=(1<<31)-1;
int b[105][105]={0};//设备i被厂家j生产时的带宽B
int p[105][105]={0};//设备i被厂家j生产时的价格P
int m[105];
int dp[105][500];   //表示选择[前i个]路由设备所构成带宽为j的系统所需支付的最小价格，

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&m[i]);
            for(int j=1;j<=m[i];j++)
            {
                scanf("%d%d",&b[i][j], &p[i][j]);
            }
        }

        for(int i=1;i<105;i++)
        {
            for(int j=0;j<500;j++)
            {
                dp[i][j]=inf;
            }
        }

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m[i];j++)
            {
                int B=b[i][j];
                int P=p[i][j];
                if(i==1)
                {
                    dp[1][B]=min(dp[1][B], P);
                }
                else
                {
                    for(int k=1;k<B;k++)
                    {
                        if(dp[i-1][k]<inf)
                        {
                            dp[i][k]=min(dp[i][k], dp[i-1][k]+P);
                        }
                    }
                    for(int k=B;k<500;k++)
                    {
                        if(dp[i-1][k]<inf)
                        {
                            dp[i][B]=min(dp[i][B], dp[i-1][k]+P);
                        }
                    }
                }
            }
        }
        double MAX=0;
        for(int i=1;i<500;i++)
        {
            if(dp[n][i]<inf)
            {
                MAX=max(MAX, 1.0*i/dp[n][i]);
            }
        }
        printf("%.3f\n",MAX);

    }

    return 0;
}