首页 > 其他 > 详细

才艺表演「Usaco2018 Open」

时间:2019-08-20 14:11:45      阅读:53      评论:0      收藏:0      [点我收藏+]

题意

有一堆牛,每个牛有重量\(w\)与质量\(t\),现在从中选出若干头,满足:

  1. 重量总和不小于给定的\(W\)

  2. 质量总和除以重量总和最大。

求最大的商。


思路

01分数规划裸题,但是数据太水,可以大力乱搞。

子状态\(dp[i][w]\)表示选第\(i\)个之后离达到重量\(W\)距离为\(w\)的情况的最大结果。(如果超过则为0)

状态转移方程为\(dp[i][w-a[i].w]=max(dp[i][w-a[i].w],(dp[j][w]*(W-w)+a[i].t)/(W-w+a[i].w))\)

统计答案的时候统计所有的\(dp[i][0]\)即可。

代码

#include <bits/stdc++.h>

using namespace std;

namespace StandardIO {
    
    template<typename T> inline void read (T &x) {
        x=0;T f=1;char c=getchar();
        for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
        for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
        x*=f;
    }
    template<typename T> inline void write (T x) {
        if (x<0) putchar('-'),x=-x;
        if (x>=10) write(x/10);
        putchar(x%10+'0');
    }
    
}

using namespace StandardIO;

namespace Solve {
    
    const int N=252;
    
    int n,W,limit;
    double ans;
    struct node {
        int w,t;
    } a[N];
    double dp[N][1001];
    
    inline bool cmp1 (const node &x,const node &y) {
        return (x.w==y.w)?(x.t>y.t):(x.w<y.w);
    }
    inline bool cmp2 (const node &x,const node &y) {
        return static_cast<double>(x.t/x.w)<static_cast<double>(y.t/y.w);
    }
    void dfs (int pos,int tot_w,int tot_t) {
        for (register int i=pos; i<=limit; ++i) {
            if (tot_w+a[i].w>=W) ans=max(ans,static_cast<double>(tot_t+a[i].t)/(tot_w+a[i].w));
            dfs(pos+1,tot_w+a[i].w,tot_t+a[i].t);
        }
    }
    
    inline void MAIN () {
        read(n),read(W);
        for (register int i=1; i<=n; ++i) {
            read(a[i].w),read(a[i].t);
        }
        sort(a+1,a+n+1,cmp1);
        for (register int i=1; i<=n; ++i) {
            dp[i][max(0,W-a[i].w)]=static_cast<double>(a[i].t)/a[i].w;
            for (register int j=1; j<i; ++j) {
                for (register int w=max(W-a[j].w,0); w>=0; --w) {
                    if (w<a[i].w) {
                        dp[i][0]=max(dp[i][0],(dp[j][w]*(W-w)+a[i].t)/(W-w+a[i].w));
                    } else {
                        dp[i][w-a[i].w]=max(dp[i][w-a[i].w],(dp[j][w]*(W-w)+a[i].t)/(W-w+a[i].w));  
                    }
                }
            }
        }
        for (register int i=1; i<=n; ++i) {
            ans=max(ans,dp[i][0]);
        }
        write(static_cast<int>(ans*1000));
    }
    
}

int main () {
    Solve::MAIN();
}

才艺表演「Usaco2018 Open」

原文:https://www.cnblogs.com/ilverene/p/11382270.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!