9513 防空洞

时间限制:1000MS 内存限制:65535K

题型: 编程题语言: 无限制

Description

    有一天，dragon123偷偷地拿锄头在学校里挖开了一个尘封已久的防空洞。
    他在这个防空洞里面找到许多贵重的东西：一些石头和一些液体。
    dragon123知道，只要他把这些石头和液体拿出去卖，那么就一定可以赚大钱。但是，他只有一个载重量为W的瓶子来装这些东西。
    防空洞里面有很多块石头，每块石头的重量为Wi，价值为Mi，但是石头不能够砸烂，否则就不值钱了。
    此外，洞里面很多种贵重的液体。对于某种液体，洞内存储了Wi重量，且这Wi重量液体的总价值为Mi。
    液体是可以部分放进瓶子里面的。也就是说，如果洞里面有Wi重量的某种液体，那么dragon123可以带走Ws(0<=Ws<=Wi)重量。
    给出洞里面石头和液体的信息，以及瓶子的载重量W，dragon123希望你帮忙计算出他能够带回东西的最大价值。

输入格式

    输入文件的第一行是n与W。
    n是洞里面贵重物品的数量总和（包括石头与液体）。W是瓶子的载重量。N (1 <= N <= 100) 且 W (0 <= W <= 50000)
    接下来有n行，每行都有3个数字a，b，c。
    如果c是0，那么就意味着这一行表示的物品是石头。那么a就是这块石头的重量，b就是这块石头的价值。
    如果c是1，那么就意味着这一行表示的物品是液体。那么a就是这种液体在山洞中的总储量，b就是山洞中所有的这种液体的总价值。

输出格式

    输出仅有一行，表示能够获得的最大价值。保留小数点后两位小数。

输入样例

输出样例

103.85

：：一开始做这道题，没什么思路，想想用dp和用greedy，感觉都不行，现在想到了，对液体贪心，对石头dp就行了

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

typedef long long ll;
const int maxw=50000;
double dp[maxw+10];

struct node
{
    int a,b;
    bool operator <(const node t) const
    {
        return 1.0*b/a>1.0*t.b/t.a;
    }
}wa[110],st[110];

double Greed(int n,int w)
{
    double sum=0;
    int i=0;
    while(w&&i<n)
    {
        if(w>=wa[i].a)
        {
            sum+=wa[i].b;
            w-=wa[i++].a;
        }
        else
        {
            sum+=w*1.0*wa[i].b/wa[i].a;
            w=0;
        }
    }
    return sum;
}

void addwa(int n,int w)//对液体贪心
{
    for(int i=1;i<=w;i++)
        dp[i]=Greed(n,i);
}

void addst(int n,int w)//对石头dp
{
    for(int i=0;i<n;i++)
    {
        for(int j=w;j>=st[i].a;j--)
            dp[j]=max(dp[j],dp[j-st[i].a]+st[i].b);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    int n,w;
    while(~scanf("%d%d",&n,&w))
    {
        int c,i,l=0,r=0;

        memset(dp,0,sizeof(dp));
        for(i=0;i<n;i++)
        {
            scanf("%d%d%d",&st[l].a,&st[l].b,&c);
            if(c)
                wa[r++]=st[l];
            else
                l++;
        }
        sort(wa,wa+r);

        addwa(r,w);
        addst(l,w);
        printf("%.2lf
",dp[w]);
    }
    return 0;
}