JDOJ1049 采药


在JDOJ上一共有两道“采药”,一道数据比较小,另一道数据比较强。弱版可以直接01背包过不TLE,但是另一个“采药”就比较难了……

一群人用贪心过了,但是这道题实际上亮眼的是数据范围:t[i]<=10,v[i]<=10.于是这样只有最多100种药。我们只需要记录这100种药以及它们的个数,这样就构造了一个多重背包。

而多重背包我竟然不会写……最后还是用的曾经写过的板子最终A了……

附代码。

#include <cstdio>
#include <algorithm>
 
struct medicine{
    int t,v,num;
}m[100100],newm[11000];
 
int n,inm,f[100010],top,ans;
 
bool cmp(medicine tx,medicine ty)
{
    if(tx.v==ty.v) return tx.t<ty.t;
    return tx.v<ty.v;
}
 
void one(int a,int b)
{
    for(int i=inm;i>=a;--i)
    {
        if(f[i-a]!=0||i-a==0) f[i]=std::max(f[i],f[i-a]+b);
    }
    return;
}
 
void apart(int a,int b,int c)
{
    int tot=1,tmp=0;
    while(tot<c)
    {
        one(a<<tmp,b<<tmp);
        ++tmp;
        tot+=(1<<tmp);
    }
    tot-=1<<tmp;
    if(tot<c)
    {
        tmp=c-tot;
        one(a*tmp,b*tmp);
    }
    return;
}
 
int main()
{
    scanf("%d%d",&n,&inm);
    for(int i=1;i<=n;++i) scanf("%d%d",&m[i].t,&m[i].v);
    std::sort(m+1,m+n+1,cmp);
    for(int i=1;i<=n;++i)
    {
        m[i].num++;
        int tmp=i;
        while(m[i+1].t==m[i].t&&m[i+1].v==m[i].v)
        {
            ++m[tmp].num;
            m[i+1].num=-1;
            ++i;
        }
    }
    for(int i=1;i<=n;++i) if(m[i].num!=-1) apart(m[i].t,m[i].v,m[i].num);
    for(int i=0;i<=inm;++i) ans=std::max(ans,f[i]);
    printf("%d",ans);
    return 0;
}

 

声明:TonyZhao's Home|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - JDOJ1049 采药


不骗了,不骗了。
A Simple OIer fighting tooth and nail.