//题意：第一行给你两个数字，第一个是T组数据，第二个数n是接下来有几行，每一行第一个m代表这一行有几组值，d，p分别代表带块（跟家里的宽带最大允许通过字节数差不多意思）和价格，问：每一行代表一个设备，每个设备有m个厂商提供自己的产品，每一类设备选择一个厂商，共选n个设备，然后因为一个设备选择一个厂商，在这些厂商中选择一个d，带宽最小值，求得d/(p1+p2+...+pn)最大值，例如样例：第一行：150 35；第二行 155 40； 第三行：120 110 则最小值d为120 ，120/（35+40+110）即0.649
//【注意】：此题真的好恶心，跟自己菜有关系，一直按照这个思路写好的代码就是过不了，后来从新按照同样思路写了好多次写了一天终于过去了，并得到一个结论：思路决定一切，看似完全相同的代码并不代表思路相同，按照自己思路写出自己的代码，可以看题解，但要知道的是借别人的思路写出自己的代码)
//思路：这个题有多解，这里是dp解法，看到此题应该想到动态转移，那么关于求 d/p的最大值有个简单的贪心思路是尽量不断状态压缩保证p的总和相对较小，但是并不代表p越小就是题目的解，因为题目有另一不可控变量d，状态压缩同时将所有情况保存起来，所以此题关键并不是贪心求出p的最小值，而是保存所有的状态，因为d和p均为变量，只能球的所有状态一一枚举计算，当然求p有利于更快速求得答案,这里的动态方程非常简单不多说，见代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int const maxx = 1200; int dp[120][maxx]; int vis[maxx]; int main() { int t; scanf("%d", &t); while(t--){ int n; scanf("%d", &n); memset(dp, 1000000, sizeof(dp)); memset(vis, 0, sizeof(vis)); for(int i = 0; i < maxx; i++) dp[0][i] = 0; int max_d = 0; for(int i = 1; i <= n; i++){ int m; scanf("%d", &m); for(int j = 0; j < m; j++){ int d, p; scanf("%d%d", &d, &p); max_d = max(max_d, d); vis[d] = 1; for(int k = d; k < maxx; k++){ dp[i][d] = min(dp[i][d], dp[i-1][k] + p);//尽可能状态压缩求出些相对较小的p } for(int k = 0; k < d; k++){ dp[i][k] = min(dp[i-1][k] + p, dp[i][k]);//此题关键是这里和上面两步将所有状态都保存起来 } } } float ans = -1; for(int i = 0; i <= max_d; i++){ if(vis[i] && ans < (i/(float)dp[n][i])){ //这里一一运算求出最大值即可 ans = i/(float)dp[n][i]; } } printf("%.3f\n", ans); } return 0; }