要求 max{F/P},先枚举下界 lowf，再贪心求符合约束条件的 n 个最小价值和 记录 F 的离散值和去重可以大幅度常数优化

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<iterator>
using namespace std;
const int maxn = 1e5+11;
typedef pair<int,int> P;
vector<P> vec[maxn];
vector<int> F;
int n,m,x,y;
int main(){
    int T; scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        memset(vec,0,sizeof vec); F.clear();
        for(int i = 1; i <= n; i++){
            scanf("%d",&m);
            for(int j = 1; j <= m; j++){
                scanf("%d%d",&x,&y);
                vec[i].push_back(P(x,y));
                F.push_back(x);
            }
        }
        sort(F.begin(),F.end());
        vector<int>::iterator it = unique(F.begin(),F.end());
        F.erase(it,F.end());
        double ans=-1;
        long long tmp=0;
        for(int k = 0; k < F.size(); k++){//enum the lb of F
            int lowf=F[k];
            tmp=0;
            bool flag=0;
            for(int i = 1; i <= n; i++){
                int mn=0x7fffffff;
                for(int tt = 0; tt < vec[i].size(); tt++){
                    P t=vec[i][tt];
                    if(t.first>=lowf){
                        mn=min(mn,t.second);
                    }
                }
                if(mn==0x7fffffff)flag=1;
                tmp+=mn;
            }
            if(flag==1) continue;
            ans=max(ans,(double)lowf/tmp);
        }
        printf("%.3lf\n",ans);
    }
    return 0;
}

DP 写法

因为二维的 dp[][k] 是滚动更新的，所以每次更新当前最小值是 dp[i-1][k] 必然存在最优解

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<iterator>
using namespace std;
const int maxn = 1211;
const int oo = 0x3f3f3f3f;
typedef pair<int,int> P;
vector<P> vec[maxn];
vector<int> F;
int dp[123][maxn];//mincost when  lowf of [1..i] = j 
int n,m,x,y;
int main(){
    int T; scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        memset(vec,0,sizeof vec);
        for(int i = 1; i <= n; i++){
            scanf("%d",&m);
            for(int j = 1; j <= m; j++){
                scanf("%d%d",&x,&y);
                vec[i].push_back(P(x,y));
            }
        }
        memset(dp,oo,sizeof dp);
        for(int i = 0; i < vec[1].size(); i++){
            P t = vec[1][i];
            dp[1][t.first]=min(dp[1][t.first],t.second);
        }
        for(int i = 2; i <= n; i++){
            for(int j = 0; j < vec[i].size(); j++){
                P t=vec[i][j];
                for(int k = 0; k < maxn; k++){
                    if(dp[i-1][k]!=oo){
                        if(k<=t.first)
                            dp[i][k]=min(dp[i][k],dp[i-1][k]+t.second);
                        else
                            dp[i][t.first]=min(dp[i][t.first],dp[i-1][k]+t.second);
                    }   
                }
            }
        }
        double ans=-1;
        for(int i = 0; i < maxn; i++) if(dp[n][i]!=oo) ans=max(ans,(double)i/dp[n][i]);
        printf("%.3lf\n",ans);
    }
    return 0;
}