分数规划 - 洛谷保存站

对于$ \frac{\sum a_i\times c_i}{\sum b_i\times c_i} $ ，$ c_i\in {0,1} $ ,通过对 $ c_i $ 的合理取值使结果最大化，这类问题被称为分数规划问题。

分数规划问题通常使用二分解决。

考虑二分到一个 $ mid $ 值，问题转化为判断 $ \frac{\sum a_i\times c_i}{\sum b_i\times c_i} - mid \ge 0 $ 。

对式子进行转化，$ \sum (a_i-mid\times b_i)\times c_i \ge 0 $ 。

这时，问题就已经解决了，每次二分时，先处理出所有的 $ a_i-mid\times b_i $ ,然后贪心的选择大于 $ 0 $ 的结果，最后结果大于 $ 0 $ 即为合法。（在没有选择个数限制时，有一个大于 $ 0 $ 即为合法）这便是最简单的分数规划问题。

# 例题：

[P4377](https://www.luogu.com.cn/problem/P4377)

这题加入了重量和至少为 $ W $ 的限制，考虑每次二分做一次动态规划，$ dp[j] $ 表示重量和为 $ j $ 时 $ \sum a_i-mid\times b_i $ 的最大值，重量大于 $ W $ 的一律视为 $ W $ 考虑，最后判断 $ dp[w]\ge 0 $ 即可。

```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
int read(){
    int x=0,f=1;
    char ac=getchar();
    while(ac<'0'||ac>'9'){
        if(ac=='-') f=-1;
        ac=getchar();
    }
    while(ac>='0'&&ac<='9'){
        x=(x<<3)+(x<<1)+(ac-'0');
        ac=getchar();
    }
    return x*f;
}
int n,maxn,w[255],t[255];
long long dp[1005];
bool check(int x){
    memset(dp,-0x3f,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=maxn;j>=0;j--){
            int num=std::min(maxn,j+w[i]);
            dp[num]=std::max(dp[num],dp[j]+t[i]-1ll*w[i]*x);
        }
    }
    return dp[maxn]>=0;
}
int main(){
    n=read(),maxn=read();
    for(int i=1;i<=n;i++){
        w[i]=read(),t[i]=read();
        t[i]*=1000;
    }
    int l=0,r=250000,ans=0;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)){
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
    }
    printf("%d",ans);
    return 0;
}
```

[P4322](https://www.luogu.com.cn/problem/P4322)

加入选择一个节点必须选择其父节点的限制。

同样考虑每次 $ check $ 动规解决，直接暴力树上 $ dp $ 可能会炸，考虑基于题目限制的一种优化：树形背包。即通过预处理时间戳，使父节点的时间戳大于子节点的时间戳，将树转化为一个线性序列进行动规，具体实现参考代码。

```cpp
#include<cstdio>
#include<algorithm>
int read(){
    int x=0,f=1;
    char ac=getchar();
    while(ac<'0'||ac>'9'){
        if(ac=='-') f=-1;
        ac=getchar();
    }
    while(ac>='0'&&ac<='9'){
        x=(x<<3)+(x<<1)+(ac-'0');
        ac=getchar();
    }
    return x*f;
}
const double eps=1e-5;
int n,k,s[2505],p[2505],t[2505],nxt[2505],h[2505],cnt,size[2505],num,dfn[2505];
double dp[2505][2505];
void add(int u,int v){
    t[++cnt]=v;
    nxt[cnt]=h[u];
    h[u]=cnt;
}
void dfs(int u){
    size[u]=1;
    for(int i=h[u];i;i=nxt[i]){
        dfs(t[i]);
        size[u]+=size[t[i]];
    }
    dfn[++num]=u;
}
bool check(double x){
    for(int i=0;i<=num;i++){
        for(int j=1;j<=k;j++){
            dp[i][j]=-1e9;
        }
    }
    for(int i=1;i<=num;i++){
        for(int j=1;j<=k;j++){
            dp[i][j]=std::max(dp[i-1][j-1]+p[dfn[i]]-x*s[dfn[i]],dp[i-size[dfn[i]]][j]);
        }
    }
    return dp[num][k]>=0;
}
int main(){
    k=read(),n=read();
    k++;
    for(int i=1;i<=n;i++){
        s[i]=read(),p[i]=read();
        int fa=read();
        add(fa,i);
    }
    dfs(0);
    double l=0,r=10000,ans=0;
    while(l+eps<=r){
        double mid=(l+r)/2;
        if(check(mid)){
            l=mid+eps;
            ans=mid;
        }
        else r=mid-eps;
    }
    printf("%.3lf",ans);
    return 0;
}
```

[P1642](https://www.luogu.com.cn/problem/P1642)

限制条件为选出的点联通，在树上 $ dp $ 时，对于每个点 $ u $ ,在统计其子树答案时强制选点 $ u $ 即可，思路较为简单，不放代码。

[P6087](https://www.luogu.com.cn/problem/P6087)

题目给的式子很套路，容易想到当最大值和最小值位于左右两端点时答案最优。

然后考虑分为两部分贡献。

对于最大值和最小值之间长度小于 $ L $ 的，把长度拓展到 $ L $ 一定最优，问题转化为询问连续一段长为 $ L $ 的序列中的最大值和最小值，单调队列裸题。

对于最大值和最小值之间长度大于等于 $ L $ 的，考虑用分数规划求解，此时再分两种小情况，当最大值位于左端点 $ i $ ，最小值位于右端点 $ j $ ，$ check $ 的式子为 $ (a_i+i\times mid)-(a_j+j\times mid) \ge k\times mid $ ,维护一个单调队列，每次取出符合条件的 $ a_j+j\times mid $ 最小的 $ j $ ,符合条件则 $ check $ 通过，当最大值位于右端点 $ j $ ，最小值位于左端点 $ i $ ，$ check $ 的式子为 $ (a_j-j\times mid)-(a_i-i\times mid)\ge k\times mid $ ,同样可以通过单调队列维护。

```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
int read(){
    int x=0,f=1;
    char ac=getchar();
    while(ac<'0'||ac>'9'){
        if(ac=='-') f=-1;
        ac=getchar();
    }
    while(ac>='0'&&ac<='9'){
        x=(x<<3)+(x<<1)+(ac-'0');
        ac=getchar();
    }
    return x*f;
}
const double eps=1e-6;
int t,n,k,minx,maxx,a[50005],q1[50005],q2[50005],head1,head2,tail1,tail2;
double b1[50005],b2[50005];
double init(){
    memset(q1,0,sizeof(q1));
    memset(q2,0,sizeof(q2));
    head1=head2=tail1=tail2=0;
    double sum=0;
    for(int i=1;i<=n;i++){
        while(head1<tail1&&q1[head1]+minx<=i) head1++;
        while(head2<tail2&&q2[head2]+minx<=i) head2++;
        while(head1<tail1&&a[q1[tail1-1]]<=a[i]) tail1--;
        while(head2<tail2&&a[q2[tail2-1]]>=a[i]) tail2--;
        q1[tail1]=i;
        q2[tail2]=i;
        tail1++,tail2++;
        sum=std::max(sum,(a[q1[head1]]-a[q2[head2]])/(1.0*minx-1+k));
    }
    return sum;
}//对于长度小于minx的区间，直接扩充到minx的长度是最优的，用单调队列维护
bool check(double x){
    memset(q1,0,sizeof(q1));
    memset(q2,0,sizeof(q2));
    head1=head2=tail1=tail2=0;
    for(int i=1;i<=n;i++){
        b1[i]=a[i]-x*i;
        b2[i]=a[i]+x*i;
    }
    for(int i=minx;i<=n;i++){
        while(head1<tail1&&q1[head1]+maxx<=i) head1++;
        while(head2<tail2&&q2[head2]+maxx<=i) head2++;
        while(head1<tail1&&b1[q1[tail1-1]]>=b1[i-minx+1]) tail1--;
        while(head2<tail2&&b2[q2[tail2-1]]<=b2[i-minx+1]) tail2--;
        q1[tail1]=i-minx+1;
        q2[tail2]=i-minx+1;
        tail1++,tail2++; 
        if(b1[i]-b1[q1[head1]]>=x*k) return 1;
        if(b2[q2[head2]]-b2[i]>=x*k) return 1;
    }
    return 0;
}
int main(){
    t=read();
    while(t--){
        n=read(),k=read(),minx=read(),maxx=read();
        for(int i=1;i<=n;i++) a[i]=read();
        double l=0,r=1000,ans=0;
        while(l+eps<r){
            double mid=(l+r)/2;
            if(check(mid)){
                ans=mid;
                l=mid;
            }
            else r=mid;
        }
        printf("%.4lf\n",std::max(l,init()));
    }
    return 0;
}
```

正在渲染内容...