题意：一个系统由n个设备组成，每个设备可以由mi个厂商提供，每个设备你可以选一个厂商，在你选定的厂商的设备中，b（带宽）是所选设备中b值最小的，类似于短板效应，p是所有价格之和，要求b/p最小。（看了很久才懂了题意，~~~要史了）
题解：dp[ i ][ j ]表示选了i个设备，带宽最小为j所用到的最小花费。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 7 const int INF=1e8; 8 9 int kase,n,m; 10 int dp[105][1005]; 11 12 void Inite(){ 13 for(int i=0;i<105;i++) 14 for(int j=0;j<1005;j++) dp[i][j]=INF; 15 } 16 17 void Print(){ 18 double ans=0; 19 for(int i=1;i<1005;i++) if(dp[n][i]!=INF) ans=max(ans,(double)i/(double)dp[n][i]); 20 printf("%.3lf\n",ans); 21 } 22 23 void Solve(){ 24 cin>>n; 25 for(int i=1;i<=n;i++){ 26 cin>>m; 27 for(int j=1;j<=m;j++){ 28 int a,b; 29 scanf("%d%d",&a,&b); 30 if(i==1){ dp[1][a]=b; continue;} 31 for(int k=0;k<1005;k++){ 32 if(dp[i-1][k]!=INF){ 33 if(k<=a) dp[i][k]=min(dp[i][k],dp[i-1][k]+b); 34 else dp[i][a]=min(dp[i][a],dp[i-1][k]+b); 35 } 36 } 37 } 38 } 39 Print(); 40 } 41 42 int main() 43 { cin>>kase; 44 while(kase--){ 45 Inite(); 46 Solve(); 47 } 48 return 0; 49 }