本题一看似乎是递归回溯剪枝的方法，我一提交，结果超时。

然后又好像是使用DP，还可能我剪枝不够。

想了很久，无奈忍不住偷看了下提示，发现方法真多，有贪心，DP，有高级剪枝的，还有三分法的，八仙过海各显神通啊。

坏习惯了，没思考够深入就偷看提示了。

幸好及时回头，还不需要看别人的代码了。自己做出来之后，有空看看多种解法的代码也好。

然后我想出自己的思路了，使用贪心，剪枝，DP综合优化下，呵呵，最后程序有点复杂，优化到了16ms，运气好点，或者vector换成原始数组的话，应该可以0MS了。

总体思路就是：

1 利用STL 的set容器记录有多少不同的B值

2 根据不同的B值，用表tbl记录该B值下的最优解

最后比较所有B值下的最优解，得出最终最优解。

下面是优化过的程序，用了不少技巧，加了注释，希望提高参考价值吧。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; const int MAX_N = 101; int N, M; struct BP { int B, P; bool operator<(const BP &b) const { return B < b.B; } }; BP arr[MAX_N][MAX_N]; float DP(set
        
          &bset) { for (int i = 0; i < N; i++) { for (int j = arr[i][0].B-1; j > 0 ; j--) { arr[i][j].P = min(arr[i][j].P, arr[i][j+1].P); }//计算结果为当前大于某个B的最小P值，优化下面填表 } vector
         
           bvec(bset.begin(), bset.end()); int M = (int)bvec.size(); //总共有多少个不同的B值 vector
          
            > tbl(N, vector
           
            (M));//记录当前B下的最优P值 vector
            
              idx(N, 1); //arr行的当前下标 for (int j = 0; j < M; j++) { for (int i = 0; i < N; i++) { for ( ; idx[i] <= arr[i][0].B; idx[i]++) { if (arr[i][idx[i]].B >= bvec[j]) { tbl[i][j] = arr[i][idx[i]].P; break; } } if (idx[i] > arr[i][0].B)//某行无法选出比B更大的值了 { tbl[0][j] = -1;//做好标志，剪枝 goto out; } } } out:; float ans = 0.0f; for (int j = 0; j < M && tbl[0][j] != -1; j++) { int totalP = 0; for (int i = 0; i < N; i++) { totalP += tbl[i][j]; } ans = max(ans, float(bvec[j])/float(totalP)); } return ans; } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d", &N); set
             
               bset; for (int i = 0; i < N; i++) { scanf("%d", &arr[i][0].B); //记录当前维长度 for (int j = 1; j <= arr[i][0].B; j++) { scanf("%d %d", &arr[i][j].B, &arr[i][j].P); bset.insert(arr[i][j].B);//记录有多少个不同的B值 } sort(arr[i]+1, arr[i]+arr[i][0].B+1);//每维按B值由小到大排序 } printf("%.3f\n", DP(bset)); } return 0; }